LeetCode 链表 Swift 练习

发表于 更新于 分类于 阅读次数：

今天开始 LeetCode 链表。

Singly Linked List

Design Linked List

707-c1.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
//
//  707-c1.swift
//  LeetCode
//
//  Created by nuomi1 on 2021/5/19.
//

// Design Linked List
// https://leetcode.com/explore/learn/card/linked-list/209/singly-linked-list/1290/
// https://leetcode.com/problems/design-linked-list/

// 设计链表
// https://leetcode-cn.com/leetbook/read/linked-list/jy291/
// https://leetcode-cn.com/problems/design-linked-list/

// MARK: 单链表

class MyLinkedList {

    private class Node {
        let val: Int
        var next: Node?

        init(val: Int, next: Node? = nil) {
            self.val = val
            self.next = next
        }
    }

    private var size: Int
    private var head: Node?

    init() {
        size = 0
        head = Node(val: 0)
    }

    func get(_ index: Int) -> Int {
        guard 0 ..< size ~= index else { return -1 }

        var curr = head

        for _ in 0 ..< index + 1 {
            curr = curr?.next
        }

        return curr!.val
    }

    func addAtHead(_ val: Int) {
        addAtIndex(0, val)
    }

    func addAtTail(_ val: Int) {
        addAtIndex(size, val)
    }

    func addAtIndex(_ index: Int, _ val: Int) {
        guard 0 ... size ~= index else { return }

        var pred = head

        for _ in 0 ..< index {
            pred = pred?.next
        }

        size += 1
        let toAdd = Node(val: val)
        toAdd.next = pred?.next
        pred?.next = toAdd
    }

    func deleteAtIndex(_ index: Int) {
        guard 0 ..< size ~= index else { return }

        var pred = head

        for _ in 0 ..< index {
            pred = pred?.next
        }

        size -= 1
        pred?.next = pred?.next?.next
    }
}

Two Pointer Technique

Linked List Cycle

141-e2.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//
//  141-e2.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/11.
//  Updated by nuomi1 on 2021/5/20.
//

// Linked List Cycle
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/773/
// https://leetcode.com/explore/learn/card/linked-list/214/two-pointer-technique/1212/
// https://leetcode.com/problems/linked-list-cycle/

// 环形链表
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnwzei/
// https://leetcode-cn.com/leetbook/read/linked-list/jbex5/
// https://leetcode-cn.com/problems/linked-list-cycle/

// MARK: Floyd's Cycle Finding Algorithm

func hasCycle(_ head: ListNode?) -> Bool {
    var fastNode = head
    var slowNode = head

    while slowNode != nil, fastNode != nil, fastNode?.next != nil {
        fastNode = fastNode?.next?.next
        slowNode = slowNode?.next

        if fastNode === slowNode {
            return true
        }
    }

    return false
}

Linked List Cycle II

142-c2.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//
//  142-c2.swift
//  LeetCode
//
//  Created by nuomi1 on 2021/5/21.
//

// Linked List Cycle II
// https://leetcode.com/explore/learn/card/linked-list/214/two-pointer-technique/1214/
// https://leetcode.com/problems/linked-list-cycle-ii/

// 环形链表 II
// https://leetcode-cn.com/leetbook/read/linked-list/jjhf6/
// https://leetcode-cn.com/problems/linked-list-cycle-ii/

// MARK: 快慢指针

func detectCycle(_ head: ListNode?) -> ListNode? {
    var fastNode = head
    var slowNode = head

    while slowNode != nil, fastNode != nil, fastNode?.next != nil {
        fastNode = fastNode?.next?.next
        slowNode = slowNode?.next

        if fastNode === slowNode {
            var anotherNode = head

            while anotherNode !== slowNode {
                anotherNode = anotherNode?.next
                slowNode = slowNode?.next
            }

            return anotherNode
        }
    }

    return nil
}

Intersection of Two Linked Lists

160-e3.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//
//  160-e3.swift
//  LeetCode
//
//  Created by nuomi1 on 2021/5/22.
//

// Intersection of Two Linked Lists
// https://leetcode.com/explore/learn/card/linked-list/214/two-pointer-technique/1215/
// https://leetcode.com/problems/intersection-of-two-linked-lists/

// 相交链表
// https://leetcode-cn.com/leetbook/read/linked-list/jjbj2/
// https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

// MARK: Two Pointers

func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
    var nodeA = headA
    var nodeB = headB

    while nodeA !== nodeB {
        nodeA = nodeA == nil ? headB : nodeA?.next
        nodeB = nodeB == nil ? headA : nodeB?.next
    }

    return nodeA
}

Remove Nth Node From End of List

19-e2.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//
//  19-e2.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/7.
//  Updated by nuomi1 on 2021/5/23.
//

// Remove Nth Node From End of List
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/603/
// https://leetcode.com/explore/learn/card/linked-list/214/two-pointer-technique/1296/
// https://leetcode.com/problems/remove-nth-node-from-end-of-list/

// 删除链表的倒数第N个节点
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn2925/
// https://leetcode-cn.com/leetbook/read/linked-list/jf1cc/
// https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

// MARK: One pass algorithm

func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
    var fastNode = head
    var slowNode = head

    for _ in 0 ..< n {
        fastNode = fastNode?.next
    }

    guard fastNode != nil else {
        return head?.next
    }

    while fastNode?.next != nil {
        fastNode = fastNode?.next
        slowNode = slowNode?.next
    }

    slowNode?.next = slowNode?.next?.next
    return head
}
19-s1.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//
//  19-s1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/7.
//  Updated by nuomi1 on 2021/5/23.
//

// Remove Nth Node From End of List
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/603/
// https://leetcode.com/explore/learn/card/linked-list/214/two-pointer-technique/1296/
// https://leetcode.com/problems/remove-nth-node-from-end-of-list/

// 删除链表的倒数第N个节点
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn2925/
// https://leetcode-cn.com/leetbook/read/linked-list/jf1cc/
// https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
    var fastNode = head
    var slowNode: ListNode?

    var count = n

    while fastNode != nil {
        if count <= 0 {
            slowNode = slowNode == nil ? head : slowNode?.next
        }

        fastNode = fastNode?.next

        count -= 1
    }

    guard slowNode != nil else {
        return head?.next
    }

    slowNode?.next = slowNode?.next?.next
    return head
}

Classic Problems

Reverse Linked List

206-e1.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//
//  206-e1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/8.
//  Updated by nuomi1 on 2021/5/24.
//

// Reverse Linked List
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/560/
// https://leetcode.com/explore/learn/card/linked-list/219/classic-problems/1205/
// https://leetcode.com/problems/reverse-linked-list/

// 反转链表
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnnhm6/
// https://leetcode-cn.com/leetbook/read/linked-list/f58sg/
// https://leetcode-cn.com/problems/reverse-linked-list/

// MARK: Iterative

func reverseList(_ head: ListNode?) -> ListNode? {
    var newHead: ListNode?
    var currentNode = head

    while currentNode != nil {
        let tempNode = currentNode?.next
        currentNode?.next = newHead
        newHead = currentNode
        currentNode = tempNode
    }

    return newHead
}

Remove Linked List Elements

203-c1.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//
//  203-c1.swift
//  LeetCode
//
//  Created by nuomi1 on 2021/5/25.
//

// Remove Linked List Elements
// https://leetcode.com/explore/learn/card/linked-list/219/classic-problems/1207/
// https://leetcode.com/problems/remove-linked-list-elements/

// 移除链表元素
// https://leetcode-cn.com/leetbook/read/linked-list/f9izv/
// https://leetcode-cn.com/problems/remove-linked-list-elements/

// MARK: 哨兵节点

func removeElements(_ head: ListNode?, _ val: Int) -> ListNode? {
    let sentinelHead: ListNode? = ListNode(0)
    sentinelHead?.next = head

    var previousNode = sentinelHead
    var currentNode = head

    while currentNode != nil {
        if currentNode?.val == val {
            previousNode?.next = currentNode?.next
        } else {
            previousNode = currentNode
        }

        currentNode = currentNode?.next
    }

    return sentinelHead?.next
}

Odd Even Linked List

328-e1.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//
//  328-e1.swift
//  LeetCode
//
//  Created by nuomi1 on 2021/5/26.
//

// Odd Even Linked List
// https://leetcode.com/explore/learn/card/linked-list/219/classic-problems/1208/
// https://leetcode.com/problems/odd-even-linked-list/

// 奇偶链表
// https://leetcode-cn.com/leetbook/read/linked-list/fe0kj/
// https://leetcode-cn.com/problems/odd-even-linked-list/

func oddEvenList(_ head: ListNode?) -> ListNode? {
    var oddNode = head
    var evenNode = head?.next

    let evenHead = evenNode

    while evenNode != nil, evenNode?.next != nil {
        oddNode?.next = evenNode?.next
        oddNode = oddNode?.next
        evenNode?.next = oddNode?.next
        evenNode = evenNode?.next
    }

    oddNode?.next = evenHead

    return head
}

Palindrome Linked List

234-c1.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//
//  234-c1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/10.
//  Updated by nuomi1 on 2021/5/27.
//

// Palindrome Linked List
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/772/
// https://leetcode.com/explore/learn/card/linked-list/219/classic-problems/1209/
// https://leetcode.com/problems/palindrome-linked-list/

// 回文链表
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnv1oc/
// https://leetcode-cn.com/leetbook/read/linked-list/fov6t/
// https://leetcode-cn.com/problems/palindrome-linked-list/

// MARK: 将值复制到数组中后用双指针法

func isPalindrome(_ head: ListNode?) -> Bool {
    var currentNode = head
    var nodes = [ListNode]()

    while currentNode != nil {
        nodes.append(currentNode!)
        currentNode = currentNode?.next
    }

    var leftIndex = nodes.startIndex
    var rightIndex = nodes.index(before: nodes.endIndex)

    while leftIndex < rightIndex {
        guard nodes[leftIndex].val == nodes[rightIndex].val else {
            return false
        }

        nodes.formIndex(after: &leftIndex)
        nodes.formIndex(before: &rightIndex)
    }

    return true
}

Doubly Linked List

Design Linked List

707-c2.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
//
//  707-c2.swift
//  LeetCode
//
//  Created by nuomi1 on 2021/5/28.
//

// Design Linked List
// https://leetcode.com/explore/learn/card/linked-list/210/doubly-linked-list/1294/
// https://leetcode.com/problems/design-linked-list/

// 设计链表
// https://leetcode-cn.com/leetbook/read/linked-list/fabl3/
// https://leetcode-cn.com/problems/design-linked-list/

// MARK: 双链表

class MyLinkedList {

    private class Node {
        let val: Int
        var prev: Node?
        var next: Node?

        init(val: Int, prev: Node? = nil, next: Node? = nil) {
            self.val = val
            self.prev = prev
            self.next = next
        }
    }

    private var size: Int
    private var head: Node?
    private var tail: Node?

    init() {
        size = 0
        head = Node(val: 0)
        tail = Node(val: 0)
        head?.next = tail
        tail?.prev = head
    }

    func get(_ index: Int) -> Int {
        guard 0 ..< size ~= index else { return -1 }

        var curr: Node?

        let leftIndex = index + 1
        let rightIndex = size - index

        if leftIndex < rightIndex {
            curr = head

            for _ in 0 ..< leftIndex {
                curr = curr?.next
            }
        } else {
            curr = tail

            for _ in 0 ..< rightIndex {
                curr = curr?.prev
            }
        }

        return curr!.val
    }

    func addAtHead(_ val: Int) {
        addAtIndex(0, val)
    }

    func addAtTail(_ val: Int) {
        addAtIndex(size, val)
    }

    func addAtIndex(_ index: Int, _ val: Int) {
        guard 0 ... size ~= index else { return }

        var pred: Node?
        var succ: Node?

        let leftIndex = index
        let rightIndex = size - index

        if leftIndex < rightIndex {
            pred = head

            for _ in 0 ..< leftIndex {
                pred = pred?.next
            }

            succ = pred?.next
        } else {
            succ = tail

            for _ in 0 ..< rightIndex {
                succ = succ?.prev
            }

            pred = succ?.prev
        }

        size += 1
        let toAdd = Node(val: val)
        toAdd.prev = pred
        toAdd.next = succ
        pred?.next = toAdd
        succ?.prev = toAdd
    }

    func deleteAtIndex(_ index: Int) {
        guard 0 ..< size ~= index else { return }

        var pred: Node?
        var succ: Node?

        let leftIndex = index
        let rightIndex = size - index

        if leftIndex < rightIndex {
            pred = head

            for _ in 0 ..< leftIndex {
                pred = pred?.next
            }

            succ = pred?.next?.next
        } else {
            succ = tail

            for _ in 0 ..< rightIndex - 1 {
                succ = succ?.prev
            }

            pred = succ?.prev?.prev
        }

        size -= 1
        pred?.next = succ
        succ?.prev = pred
    }
}

Conclusion

Merge Two Sorted Lists

21-c1.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//
//  21-c1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/9.
//  Updated by nuomi1 on 2021/5/29.
//

// Merge Two Sorted Lists
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/771/
// https://leetcode.com/explore/learn/card/linked-list/213/conclusion/1227/
// https://leetcode.com/problems/merge-two-sorted-lists/

// 合并两个有序链表
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnnbp2/
// https://leetcode-cn.com/leetbook/read/linked-list/fnzd1/
// https://leetcode-cn.com/problems/merge-two-sorted-lists/

// MARK: 递归

func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    guard let list1 = l1, let list2 = l2 else {
        return l1 ?? l2
    }

    let list3: ListNode?

    if list1.val > list2.val {
        list3 = list2
        list3?.next = mergeTwoLists(list1, list2.next)
    } else {
        list3 = list1
        list3?.next = mergeTwoLists(list1.next, list2)
    }

    return list3
}
21-s1.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//
//  21-s1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/9.
//  Updated by nuomi1 on 2021/5/29.
//

// Merge Two Sorted Lists
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/771/
// https://leetcode.com/explore/learn/card/linked-list/213/conclusion/1227/
// https://leetcode.com/problems/merge-two-sorted-lists/

// 合并两个有序链表
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnnbp2/
// https://leetcode-cn.com/leetbook/read/linked-list/fnzd1/
// https://leetcode-cn.com/problems/merge-two-sorted-lists/

func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    guard let list1 = l1, let list2 = l2 else {
        return l1 ?? l2
    }

    var list3: ListNode?

    var node1: ListNode? = list1
    var node2: ListNode? = list2
    var node3: ListNode? = ListNode(0)

    while node1 != nil, node2 != nil {
        if node1!.val > node2!.val {
            node3?.next = node2
            node2 = node2?.next
        } else {
            node3?.next = node1
            node1 = node1?.next
        }

        // 跳过第一个无用结点
        if list3 == nil {
            list3 = node3?.next
        }

        node3 = node3?.next
    }

    if node1 != nil {
        node3?.next = node1
    }

    if node2 != nil {
        node3?.next = node2
    }

    return list3
}

Add Two Numbers

2-e1.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//
//  2-e1.swift
//  LeetCode
//
//  Created by nuomi1 on 2021/5/30.
//

// Add Two Numbers
// https://leetcode.com/explore/learn/card/linked-list/213/conclusion/1228/
// https://leetcode.com/problems/add-two-numbers/

// 两数相加
// https://leetcode-cn.com/leetbook/read/linked-list/fv6w7/
// https://leetcode-cn.com/problems/add-two-numbers/

// MARK: Elementary Math

func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    let list3: ListNode? = ListNode(0)

    var node1 = l1
    var node2 = l2
    var node3 = list3

    var quotient: Int = 0
    var remainder: Int = 0

    while node1 != nil || node2 != nil {
        let sum = (node1?.val ?? 0) + (node2?.val ?? 0) + quotient
        (quotient, remainder) = sum.quotientAndRemainder(dividingBy: 10)

        node3?.next = ListNode(remainder)

        node1 = node1?.next
        node2 = node2?.next
        node3 = node3?.next
    }

    if quotient > 0 {
        node3?.next = ListNode(quotient)
    }

    return list3?.next
}

Flatten a Multilevel Doubly Linked List

430-s1.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//
//  430-s1.swift
//  LeetCode
//
//  Created by nuomi1 on 2021/5/31.
//

// Flatten a Multilevel Doubly Linked List
// https://leetcode.com/explore/learn/card/linked-list/213/conclusion/1225/
// https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/

// 扁平化多级双向链表
// https://leetcode-cn.com/leetbook/read/linked-list/fw8v5/
// https://leetcode-cn.com/problems/flatten-a-multilevel-doubly-linked-list/

func flatten(_ head: Node?) -> Node? {
    var node = head

    var stack: [Node] = []

    while node != nil {
        if let childNode = node?.child {
            if let nextNode = node?.next {
                stack.append(nextNode)
            }

            node?.next = childNode
            childNode.prev = node
            node?.child = nil
        } else if node?.next == nil {
            if !stack.isEmpty {
                let previousNode = stack.removeLast()

                node?.next = previousNode
                previousNode.prev = node
            }
        }

        node = node?.next
    }

    return head
}

Copy List with Random Pointer

138-c3.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//
//  138-c3.swift
//  LeetCode
//
//  Created by nuomi1 on 2021/6/1.
//

// Copy List with Random Pointer
// https://leetcode.com/explore/learn/card/linked-list/213/conclusion/1229/
// https://leetcode.com/problems/copy-list-with-random-pointer/

// 复制带随机指针的链表
// https://leetcode-cn.com/leetbook/read/linked-list/fdi26/
// https://leetcode-cn.com/problems/copy-list-with-random-pointer/

// MARK: O(1) 空间的迭代

func copyRandomList(_ head: Node?) -> Node? {
    var node = head

    while node != nil {
        let nextNode = Node(node!.val)
        nextNode.next = node?.next
        node?.next = nextNode

        node = nextNode.next
    }

    node = head

    while node != nil {
        node?.next?.random = node?.random?.next

        node = node?.next?.next
    }

    var oldNode = head
    var newNode = head?.next

    let newHead = newNode

    while oldNode != nil {
        oldNode?.next = oldNode?.next?.next
        newNode?.next = newNode?.next?.next

        oldNode = oldNode?.next
        newNode = newNode?.next
    }

    return newHead
}

Rotate List

61-c1.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//
//  61-c1.swift
//  LeetCode
//
//  Created by nuomi1 on 2021/6/2.
//

// Rotate List
// https://leetcode.com/explore/learn/card/linked-list/213/conclusion/1295/
// https://leetcode.com/problems/rotate-list/

// 旋转链表
// https://leetcode-cn.com/leetbook/read/linked-list/f00a2/
// https://leetcode-cn.com/problems/rotate-list/

// MARK: 闭合为环

func rotateRight(_ head: ListNode?, _ k: Int) -> ListNode? {
    guard k > 0 else {
        return head
    }

    var count = 1
    var node = head

    while node?.next != nil {
        count += 1

        node = node?.next
    }

    var addCount = count - k % count

    node?.next = head

    while addCount > 0 {
        node = node?.next

        addCount -= 1
    }

    let newHead = node?.next
    node?.next = nil

    return newHead
}