反转链表

• 在线：LeetCode: 206

题目

Reverse a singly linked list.

JavaScript

function ListNode(val) {
  this.val = val;
  this.next = null;
}

Python

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

代码实现

方法一：递归

JavaScript

/*
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverse = function (head) {
  if (head === null || head.next === null) return head;
  let last = reverse(head.next);
  head.next.next = head;
  head.next = null;
  return last;
};

Python

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head == None or head.next == None:
            return head
        last = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return last

首先要明确递归函数的意义。reverse 函数的意义是：输入一个头节点 head，将以这个结点为头的链表反转，返回反转后的新头节点。

上图这样一个链表，通过 reverse 函数可以将其拆成如下两部分：

reverse(head.next)执行完后，会得到如下链表，刚刚已经明确过，reverse 函数会返回反转后的链表的新头，我们使用 last 来接收。

最后只需合并两个部分：

方法二：迭代

JavaScript

/*
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseLinkedlist = function (head) {
  let prev = null;
  let cur = head;
  while (cur) {
    let next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  return prev;
};

Python

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        cur = head
        while cur:
            next = cur.next
            cur.next = prev
            prev = cur
            cur = next
        return prev

复杂度

两种算法的复杂度相同为：

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

参考资料

1. labuladong 的算法小抄 之 递归反转链表的一部分，by labuladong