leetcode 206. 反转链表

题目描述

反转一个单链表。
相关话题： 链表   难度： 简单

示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

思路 1：

• 定义一个头指针，然后遍历链表，一个一个脱离后，以头插法的方式插入到新链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode newHead = null;
        for(ListNode p = head;p != null;){
            ListNode x = p;
            p = x.next;
            x.next = newHead;
            newHead = x;
        }
        return newHead;
    }
}

思路 2：

• 该思路和思路1差不多，原地反转，遍历链表，将节点一个一个脱离后插入到链表头部,如果链表为空或只有一个节点直接返回

  
  

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        for(ListNode p = head;p.next != null;){
            ListNode x = p.next;
            p.next = x.next;
            x.next = head;
            head =x;
        }
        return head;
    }
}

思路 3： 递归

• 递归思路有点抽象，主要是要知道边界(结束递归的条件)和子操作
• 以1->2->3->4->5->NULL为例，我们要得到该链表的逆，子问题就是得到2->3->4->5->NULL的逆，依次递归下去，它的递归栈如下图所示
  
  • 结束递归的条件：head == null || head.next == null
    显然，栈顶的栈帧会被返回，用一个指针newHead接受其返回值

 ListNode newHead = reverseList(head.next);

此时，newHead是指向节点5
然后递归栈中继续执行栈顶的栈帧

• 子操作：head->4->5->NULL只有两个节点，容易理解。此时链表信息为
  

要反转它，很简单，

       head.next.next = head;
       head.next = null;

然后变成，

直接返回newHead。
继续执行栈顶栈帧，head->3->4->5->NULL，此时链表信息为

执行完

       head.next.next = head;
       head.next = null;

变成

依次执行直至递归栈为空。

• 重点是要知道结束递归的条件，最小子问题和返回时的信息，从而确定子操作。
• 上面是详细分析递归的调用过程，实际上可以从一个宏观的角度来看问题
  比如要反转该链表head->1->2->3->4->5->NULL，我们在确定结束条件后，可以假定子链表head->2->3->4->5->NULL已被我们反转，其栈帧返回后的信息为
  
  (节点1的后继就是节点2)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}