题目:
题解:
1. 迭代法:
双指针迭代
我们可以申请两个指针,第一个指针叫 pre,最初是指向 null 的。
第二个指针 cur 指向 head,然后不断遍历 cur。
每次迭代到 cur,都将 cur 的 next 指向 pre,然后 pre 和 cur 前进一位。
都迭代完了(cur 变成 null 了),pre 就是最后一个节点了。
动画演示如下:
2. 递归法:
这题有个很骚气的递归解法,递归解法很不好理解,这里最好配合代码和动画一起理解。
递归的两个条件:
- 终止条件是当前节点或者下一个节点==null
- 在函数内部,改变节点的指向,也就是 head 的下一个节点指向 head 递归函数那句
head.next.next = head
很不好理解,其实就是 head 的下一个节点指向head。
递归函数中每次返回的 cur 其实只最后一个节点,在递归函数内部,改变的是当前节点的指向。
动画演示如下:
代码:
1. 代码一:(参考迭代法)
/** * code206 */
public class code206 {
public static ListNode reverseList(ListNode head) {
// 申请节点,pre和 cur,pre指向null
ListNode pre = null;
ListNode cur = head;
ListNode tmp = null;
while (cur != null) {
// 记录当前节点的下一个节点
tmp = cur.next;
// 然后将当前节点指向pre
cur.next = pre;
// pre和cur节点都前进一位
pre = cur;
cur = tmp;
}
return pre;
}
public static void print(ListNode node) {
if (node == null) {
return;
}
ListNode current = node;
while (current != null) {
System.out.print(current.val + " -> ");
current = current.next;
}
System.out.println("NULL");
}
public static void main(String[] args) {
ListNode listNode1 = new ListNode(1);
ListNode listNode2 = new ListNode(2);
ListNode listNode3 = new ListNode(3);
ListNode listNode4 = new ListNode(4);
ListNode listNode5 = new ListNode(5);
listNode1.next = listNode2;
listNode2.next = listNode3;
listNode3.next = listNode4;
listNode4.next = listNode5;
ListNode head = reverseList(listNode1);
print(head);
}
}
2. 代码二:(参考递归法)
/** * code206 */
public class code206 {
// 递归法
public static ListNode reverseList(ListNode head) {
// 递归终止条件是当前为空,或者下一个节点为空
if (head == null || head.next == null) {
return head;
}
// 这里的cur就是最后一个节点
ListNode cur = reverseList(head.next);
// 这里请配合动画演示理解
// 如果链表是 1->2->3->4->5,那么此时的cur就是5
// 而head是4,head的下一个是5,下下一个是空
// 所以需要head.next.next == head, 就是5->4
head.next.next = head;
// 防止链表循环,需要将head.next设置为空。如果使用大小为 2 的链表测试代码,则可能会捕获此错误。
head.next = null;
// 每层递归函数都返回cur,也就是最后一个节点
return cur;
}
public static void print(ListNode node) {
if (node == null) {
return;
}
ListNode current = node;
while (current != null) {
System.out.print(current.val + " -> ");
current = current.next;
}
System.out.println("NULL");
}
public static void main(String[] args) {
ListNode listNode1 = new ListNode(1);
ListNode listNode2 = new ListNode(2);
ListNode listNode3 = new ListNode(3);
ListNode listNode4 = new ListNode(4);
ListNode listNode5 = new ListNode(5);
listNode1.next = listNode2;
listNode2.next = listNode3;
listNode3.next = listNode4;
listNode4.next = listNode5;
ListNode head = reverseList(listNode1);
print(head);
}
}