链表反转

1.递归

以链表 1->2->3->4 为例子：

• 程序到达Node newHead = reverse(head.next);时进入递归
• 我们假设此时递归到了3结点，此时head=3结点，temp=3结点.next(实际上是4结点)
• 执行Node newHead = reverse(head.next);传入的head.next是4结点，返回的newHead是4结点。
• 接下来就是弹栈过程了
  • 程序继续执行 temp.next = head就相当于4->3
  • head.next = null 即把 3结点指向4结点的指针断掉。
  • 返回新链表的头结点newHead

注意：当retuen后，系统会恢复2结点压栈时的现场，此时的head=2结点；temp=2结点.next(3结点)，再进行上述的操作。最后完成整个链表的翻转。

static class ListNode {

    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
public static ListNode reverse(ListNode head) {
    if (head == null || head.next == null)
        return head;
    ListNode temp = head.next;
    ListNode newHead = reverse(head.next);
    temp.next = head;
    head.next = null;
    return newHead;
}
}

2.遍历

依旧是1->2->3->4

• 准备两个空结点 pre用来保存先前结点、next用来做临时变量
• 在头结点node遍历的时候此时为1结点
  • next = 1结点.next(2结点)
  • 1结点.next=pre(null)
  • pre = 1结点
  • node = 2结点
• 进行下一次循环node=2结点
  • next = 2结点.next(3结点)
  • 2结点.next=pre(1结点)=>即完成2->1
  • pre = 2结点
  • node = 3结点
• 进行循环…

static class ListNode {
   int val;
   ListNode next;
   ListNode(int x) { val = x; }
 }
  public static ListNode reverseList(ListNode node) {
       ListNode pre = null;
       ListNode cur = node;
       while (cur != null) {
           ListNode next = cur.next;  //将下一个节点记录
           cur.next = pre;  //当前节点指向上一个节点
           pre = cur;   //记录当前节点
           cur = next; //将下一个节点变成当前节点
       }
       return pre;
   }