代码天涯路

206.反转链表(Reverse Linked List)E

英文题目

  • Reverse a singly linked list.

  • Example:

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

  • Follow up:

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

中文题目

  • 反转一个单链表。

  • 示例:

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

  • 进阶:

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

迭代

  • 参考：【反转链表】：双指针，递归，妖魔化的双指针open in new window

  • 只要记住3个连续排布的指针的在反转前后对应意义即可

  • pre -> cur -> cur_next

  • 反转前：cur是遍历的当前指针，pre是上一个指针(初始化为None)，cur_next是下一个指针

  • 反转后：pre是反转链表后的头指针，cur是未反转链表的头指针，cur_next意义不变，是未反转链表的头指针的下一个指针

  • cur_next存在的意义是为了临时存储，在断开cur->next后仍能找到它

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

    # python: 时间 32 ms, 击败 98.67%; 内存 15.4 MB, 击败 86.42%
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre, cur = None, head
        while cur:
            cur_next = cur.next
            cur.next = pre
            pre, cur = cur, cur_next
        return pre

    // c++: 时间 8 ms, 击败 44.32%; 内存 8 MB, 击败 95.44%
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode * pre = nullptr;
        ListNode * cur = head;
        while (cur != nullptr) {
            ListNode * cur_next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = cur_next;
        }
        return pre;
    }
};

    // java: 时间 0 ms, 击败 100%; 内存 38.2 MB, 击败 61.13%
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode cur_next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = cur_next;
        }
        return pre;
    }
}

    // go: 时间 0 ms, 击败 100.00%; 内存 2.5 MB, 击败 99.92%
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var pre *ListNode
    cur := head
    for cur != nil {
        curNext := cur.Next
        cur.Next = pre
        pre, cur = cur, curNext
    }
    return pre
}

    // javascript: 时间 80 ms, 击败 32.90%; 内存 39.6 MB, 击败 56.19%
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let pre = null;
    let cur = head;
    while (cur !== null) {
        let cur_next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = cur_next;
    }
    return pre;
};

递归

  • 思路比较巧妙就是了，首先是直接找到链表的尾部结点(同二叉树的前序遍历)，递归只要看当前这个递归栈，如果只看python 的11和14行的话，意味着，找到了链尾结点并返回，这个结点同时也是新的头部结点

  • 在每一个返回的递归栈中，当前头结点扔指向下一个结点，这时，只需把头结点的下一个结点指向头结点，头结点的下一个结点变为空即可

  • 即把 head -> head.next 变成 None <- head <- head.next，这么操作的原因是再返回一个递归栈的时候，头结点仍不变指向下一个结点

  • 开始的判断中，not head是用于处理是空链表的情况，not head.next是下一个结点为空，说明这是尾部结点了

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

    # python: 时间 32 ms, 击败 98.67%; 内存 19.7 MB, 击败 9.38%
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return new_head

    // c++: 时间 0 ms, 击败 100.00%; 内存 8。4 MB, 击败 6.64%
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode * new_head = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return new_head;
    }
};

    // java: 时间 0 ms, 击败 100.00%; 内存 38.4 MB, 击败 13.68%
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
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;
    }
}

    // go: 时间 0 ms, 击败 100.00%; 内存 3 MB, 击败 22.94%
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    newHead := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return newHead
}

    // javascript: 时间 72 ms, 击败 76.63%; 内存 40.1 MB, 击败 10.73%
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    if (head === null || head.next === null) {
        return head;
    }
    let new_head = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return new_head;
};
Last Updated:
Contributors: Traum Lou, Shiqi Lu