LeetCode算法题-Reverse Linked List(Java实现)
这是悦乐书的第192次更新,第195篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第51题(顺位题号是206)。反转单链表。例如:
输入:1-> 2-> 3-> 4-> 5
输出:5-> 4-> 3-> 2-> 1
本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。
02 第一种解法
先利用递归函数,进入到最后一个节点的位置,此时需要反转指针所指向的引用方向,比如原来是n(k)–>n(k+1),现在需要反转过来变成n(k+1)–>n(k),此时需要n(k).next.next = n(k),将n(k+1)的下一个节点指向n(k),同时需要将原来n(k)节点的下一个节点指向null,即n(k).next = null。如果不指向null,会形成环,造成死循环。
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;
}
03 第二种解法
在遍历列表时,将当前节点的下一个指针更改为指向其上一个元素。由于节点没有引用其前一个节点,因此必须事先存储其前一个元素。在更改引用之前,还需要另一个指针来存储下一个节点。最后返回新的链表。
public ListNode reverseList2(ListNode head) {
ListNode result = null;
ListNode current = head;
while (current != null) {
ListNode pre = current.next;
current.next = result;
result = current;
current = pre;
}
return result;
}
04 第三种解法
利用HashMap,依次遍历head节点,将下一个节点作为key、当前节点作为value存入其中,直到其最后一个节点。新创建一个节点指向head的最后一个节点,然后开始从map中取出key所对应的value作为新节点的下一个节点。
public ListNode reverseList3(ListNode head) {
if (head == null || head.next == null) {
return head;
}
HashMap<ListNode, ListNode> nodeMap = new HashMap<>();
ListNode curr = head;
int leng = 0;
while (curr.next != null) {
nodeMap.put(curr.next, curr);
++leng;
curr = curr.next;
}
ListNode newHead = curr;
for (int i = 0; i < leng; i++) {
curr.next = nodeMap.get(curr);
curr = curr.next;
}
curr.next = null;
return newHead;
}
05 第四种解法
使用栈,借助其先进后出的特点,先将head的每一个节点入栈,然后新建一个节点res,每次出栈的节点,获取其节点值val,然后创建新的节点作为res的下一个节点。
public ListNode reverseList4(ListNode head) {
if (head == null || head.next == null) {
return head;
}
Stack<ListNode> stack = new Stack<>();
while (head != null) {
stack.push(head);
head = head.next;
}
ListNode res = new ListNode(-1);
ListNode temp = res;
while (!stack.isEmpty()) {
temp.next = new ListNode(stack.pop().val);
temp = temp.next;
}
return res.next;
}
06 第五种解法
此解法与第四种解法思路类似,只不过是将栈换成了数组,然后新建node节点,以数组最后一位元素作为节点值,然后开始循环处理每个新的节点。
public ListNode reverseList5(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ArrayList<Integer> list = new ArrayList<Integer>();
while (head != null) {
list.add(head.val);
head = head.next;
}
ListNode node = new ListNode(list.get(list.size()-1));
ListNode last = node;
for (int i=list.size()-2; i >= 0; i--) {
ListNode temp = new ListNode(list.get(i));
last.next = temp;
last = last.next;
}
return node;
}
07 小结
算法专题目前已连续日更超过一个月,算法题文章51+篇,