LeetCode-206.反转链表

发表于 分类于

题目描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

提示：

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

示例：

1
2
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
1
2
输入：head = []
输出：[]

题解

使用swift语言，需要声明链表结构：

1
2
3
4
5
6
7
8
9
// 单向链表，比如： 1->2->3->4->nil
class ListNode {
  var val: Int
  var next: ListNode?
  init(_ val: Int) {
      self.val = val
      self.next = nil
  }
}

方法一：迭代

基本思路：在遍历链表时，将当前节点的next指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

1
2
3
4
5
6
7
8
9
10
11
12
/** 反转链表：迭代*/
func reverseList(_ head: ListNode?) -> ListNode? {
  var pre: ListNode? = nil
  var cur: ListNode? = head
  while(cur !== nil) {
      let tmp = cur?.next
      cur?.next = pre
      pre = cur
      cur = tmp
  }
  return pre
}

方法二：递归

基本思路：假设链表的其余部分已经被反转，由于当前的head节点的next指针仍然指向其余部分的尾节点，所以将其余部分的末尾节点的next指向当前的head节点即可。比如，原始链表为1->2->3->4->nil，当前head为1，其余部分反转后的结果将是4->3->2->nil，则现在需要将2的节点的next指向当前的head（1）。由于head.next仍然指向val为2的节点，所以将head.next.next指向head即可。

1
2
3
4
5
6
7
8
/** 反转链表：递归*/
func reverseList2(_ head: ListNode?) -> ListNode? {
  if head == nil || head?.next == nil { return head }
  let newHead = reverseList2(head?.next)
  head?.next?.next = head
  head?.next = nil
  return newHead
}