LeetCode.206.Reverse Linked List 反转链表

题目描述

206 Reverse Linked List
https://leetcode.com/problems/reverse-linked-list/description/
https://leetcode-cn.com/problems/reverse-linked-list/

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Hint:
A linked list can be reversed either iteratively or recursively. Could you implement both?

---

相似题目

LeetCode.206.Reverse Linked List 反转链表
LeetCode.092.Reverse Linked List II 反转链表的第m到n个结点
LeetCode.025.Reverse Nodes in k-Group K 个一组翻转链表

---

解题过程

逆置单链表，非常经典的面试题，是必须滚瓜烂熟的。

使用头结点的循环头插法

我印象中有不加头结点的方法，但长时间不做题有点儿乱，想不明白，自己先尝试写了个在前面加额外头结点的方法，调试几次通过了

时间复杂度 O(n)，空间复杂度 O(1)

// 使用一个新的头结点
public ListNode reverseList(ListNode head) {
    ListNode newHead = new ListNode(0);
    newHead.next = null;
    while (null != head) {
        ListNode next = head.next; // 临时保存当前结点的下一个结点
        head.next = newHead.next; // 当前节点插入 newHead 之后
        newHead.next = head;
        head = next; // cur继续指向原链表下一个结点
    }
    return newHead.next;
}

不使用头结点的循环头插法

看网上的解法，常见的有两种，一种是循环头插法（包括使用头结点的和不使用头结点的），一种是递归，其中不使用头结点的原地逆置如下：

//原地逆置(不使用额外的头结点)
public ListNode reverseList1(ListNode head) {
    if (null == head || null == head.next) {
        return head;
    }
    ListNode cur = head.next; //cur：当前结点
    head.next = null; //head：逆置后链表的首节点，初始时是原链表的首节点(逆置后的末结点)所以next设为null
    while(cur != null){
        ListNode curNext = cur.next; //curNext：保存当前结点的下一个结点
        cur.next = head; //当前结点成为新链表表头(新链表表头挂到当前结点后)
        head = cur; //head指向新链表表头
        cur = curNext; //cur继续指向原链表下一个结点
    }
    return head;
}

还有一种写法如下，更简洁：

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

递归逆置单链表

递归法的思路是这样的：把链表看成两部分，当前表头结点head和剩下所有结点head.next，递归对剩下所有结点进行逆置得子链表newHead，然后把头结点接到逆置后的子链表newHead尾部即可。

时间复杂度 O(n)，空间复杂度 O(n)

// 递归逆置，返回反转后链表的首节点
public ListNode reverseList(ListNode head) {
    if(head==null || head.next==null) {//链表为空或只有一个结点时结束
        return head;
    }
    ListNode newHead = reverseList(head.next);//递归逆置head.next，newHead为逆置后的新链表
    head.next.next = head; //head.next是逆置后子链表newHead的最后一个结点
    head.next = null;
    return newHead;
}

这里注意，对 head.next 调用 reverseList() 后，head.next 就是逆置后子链表newHead的最后一个结点，一开始我也没想到，不知道如何获得逆置后子链表的最后一个结点，其实如果改为下面这种写法会更好理解：

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }

        ListNode next = head.next; //用next保存剩余部分的首结点(逆置后成尾结点)
        ListNode newHead = reverseList(next);
        next.next = head;
        head.next = null;

        return newHead;
    }
}

用next保存剩余部分的首结点，则逆置后自然成为返回的子链表的末尾结点。

---

GitHub代码

algorithms/leetcode/leetcode/_206_ReverseLinkedList.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_206_ReverseLinkedList.java

---