Swift 反转链表 - LeetCode

LeetCode

题目： 反转链表

反转一个单链表。 示例:

代码语言：javascript复制

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

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

方案一：

• 迭代：在链表第一个和第二个元素断开链表，保存后半段，前半段拼在新head前方，然后赋值给新head：具体如下面示意

代码语言：javascript复制

p: a -> b -> c -> d -> e -> nil
newHead = nil

temp = p.next        temp: b -> c -> d -> e -> nil
p.next = newHead        p: a -> nil
newHead = p       newHead: a -> nil
p = temp                p: b -> c -> d -> e -> nil

temp = p.next        temp: c -> d -> e -> nil
p.next = newHead        p: b -> a -> nil
newHead = p       newHead: b -> a -> nil
p = temp                p: c -> d -> e -> nil

...

newHead: d -> d -> c -> b -> a -> nil

代码一：

代码语言：javascript复制

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.next = nil
 *     }
 * }
 */
class Solution {
  func reverseList(_ head: ListNode?) -> ListNode? {
    if head == nil || head?.next == nil {
        return head
    }
    
     var newHead: ListNode? = ListNode.init(0).next
     var p = head
     while p != nil {
        let tmp = p?.next
        p?.next = newHead
        newHead = p
        p = tmp
     }
    return newHead
  }
}

方案二：

• 递归：递归找到最后一个节点作为新链表的头节点，然后再更新每一个node的next 值 ，实现链表的反转。而newhead 的值没有发生改变，为该链表的最后一个结点，所以，反转后，我们可以得到新链表的head。

1、找到最后一个节点

递归找到newHead

2、反转最后一个节点head?.next.next = head

反转最后一个节点

3、断链 head?.next = nil

断链

4、递归结束

递归结束，完成反转链表

代码二：

代码语言：javascript复制

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.next = nil
 *     }
 * }
 */
class Solution {
  func reverseList(_ head: ListNode?) -> ListNode? {
    if head == nil || head?.next == nil {
        return head
    }

    let newHead = reverseList(head?.next)
    head?.next?.next = head
    head?.next = nil
    return newHead
   }
}

swift

0 人点赞