LeetCode Linked List

发表于 更新于 Disqus： 本文字数： 7.2k 阅读时长 ≈ 7 分钟

Design Linked List

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
class Node {
    let val: Int
    var prev: Node?, next: Node?
    init(_ val: Int, prev: Node? = nil, _ next: Node? = nil) { self.val = val; self.prev = prev; self.next = next }
}

class MyLinkedList {
    private let head: Node = Node(-1), tail: Node = Node(-1)
    private var count = 0

    init() {  head.next = tail; tail.prev = head }

    func get(_ index: Int) -> Int {
        return findNode(index)?.val ?? -1
    }

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

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

    func addAtIndex(_ index: Int, _ val: Int) {
        if index >= 0 && index <= count, let node = findNode(index) {
            let newNode = Node(val)
            newNode.next = node
            newNode.prev = node.prev
            node.prev?.next = newNode
            node.prev = newNode
            count += 1
        }
        // printList()
    }

    func deleteAtIndex(_ index: Int) {
        if index >= 0 && index < count, let node = findNode(index) {
            node.prev?.next = node.next
            node.next?.prev = node.prev
            node.prev = nil; node.next = nil
            count -= 1
        }
        // printList()
    }

    private func findNode(_ index: Int) -> Node? {
        var p: Node?, i = 0
        if index <= (count/2) {
            p = head.next
            while p != nil, i < index {
                p = p?.next; i += 1
            }
        } else {
            p = tail; i = count
            while p != nil, i > index {
                p = p?.prev; i -= 1
            }
        }
        return p
    }

    private func printList() {
        var p = head.next, i: Int = 0
        while p != nil, i < count {
            print(p!.val, terminator: "->" )
            p = p?.next; i += 1
        }
        print("")
    }
}

Linked List Cycle

1
2
3
4
5
6
7
8
9
10
class Solution {
    func hasCycle(_ head: ListNode?) -> Bool {
        var fast = head?.next, slow = head
        while fast != nil, fast !== slow {
            fast = fast?.next?.next
            slow = slow?.next
        }
        return fast != nil
    }
}

Linked List Cycle II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    func detectCycle(_ head: ListNode?) -> ListNode? {
        var slow = head, fast = head?.next
        while fast != nil, fast !== slow {
            fast = fast?.next?.next
            slow = slow?.next
        }
        slow = head; fast = fast?.next
        while fast != nil, fast !== slow {
            fast = fast?.next
            slow = slow?.next
        }
        return fast
    }
}

Intersection of Two Linked Lists

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
class Solution {
    func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
        var tailA = headA
        while let p = tailA?.next { tailA = p }
        tailA?.next = headB

        let fast = detectCycle(headA)

        tailA?.next = nil

        return fast
    }

    private func detectCycle(_ head: ListNode?) -> ListNode? {
        var slow = head, fast = head?.next
        while fast != nil, fast !== slow {
            fast = fast?.next?.next
            slow = slow?.next
        }
        slow = head; fast = fast?.next
        while fast != nil, fast !== slow {
            fast = fast?.next
            slow = slow?.next
        }
        return fast
    }
}

Remove Nth Node From End of List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        var pHead = ListNode(-1, head), p0: ListNode? = pHead, p1 = p0, i = 0, j = 0
        while let q = p1?.next, j < n {
            p1 = q; j += 1
        }
        while let q = p1?.next {
            p1 = q; p0 = p0?.next
        }
        p0?.next = p0?.next?.next

        return pHead.next
    }
}

Reverse Linked List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        if head?.next == nil { return head }
        let h = reverseList(head?.next)
        head?.next?.next = head
        head?.next = nil
        return h
    }

    func reverseList(_ head: ListNode?) -> ListNode? {
        var prev: ListNode? = nil, cur = head
        while cur != nil {
            let p = cur?.next
            cur?.next = prev
            prev = cur
            cur = p
        }
        return prev
    }
}

Remove Linked List Elements

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    func removeElements(_ head: ListNode?, _ val: Int) -> ListNode? {
        let pHead = ListNode(-1, head); var p: ListNode? = pHead
        while p != nil {
            if let pn = p!.next, pn.val == val {
                p!.next = pn.next
            } else {
                p = p!.next
            }
        }
        return pHead.next
    }
}

Odd Even Linked List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    func oddEvenList(_ head: ListNode?) -> ListNode? {
        let evenHead = head, oddHead = head?.next
        var evenP = evenHead, oddP = oddHead
        while oddP?.next != nil {
            evenP?.next = evenP?.next?.next
            oddP?.next = oddP?.next?.next
            evenP = evenP?.next
            oddP = oddP?.next
        }
        evenP?.next = oddHead
        return evenHead
    }
}

Palindrome Linked List

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
class Solution {
    func isPalindrome(_ head: ListNode?) -> Bool {
        let tail = reverseList(center(head))
        return compare(head, tail)
    }

    private func compare(_ head: ListNode?, _ tail: ListNode?) -> Bool {
        var p = head, q = tail
        while q != nil {
            if p == nil || q!.val != p!.val { return false }
            p = p!.next; q = q!.next
        }
        return true
    }

    private func center(_ head: ListNode?)  -> ListNode? {
        var fast = head?.next, slow = head
        while fast != nil, fast !== slow {
            fast = fast?.next?.next
            slow = slow?.next
        }
        return slow
    }

    private func reverseList(_ head: ListNode?) -> ListNode? {
        var prev: ListNode? = nil, cur = head
        while cur != nil {
            let p = cur?.next
            cur?.next = prev
            prev = cur; cur = p
        }
        return prev
    }
}

Merge Two Sorted Lists

1
2
3
4
5
6
7
8
9
10
class Solution {
    func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        guard let p1 = l1 else { return l2 }
        guard let p2 = l2 else { return l1 }

        let (p, q) = p1.val <= p2.val ? (p1, p2) : (p2, p1)
        p.next = mergeTwoLists(p.next, q)
        return p
    }
}

Add Two Numbers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        let head = ListNode(-1)
        var p1 = l1, p2 = l2, p3: ListNode? = head, v = 0, carry = 0
        while p1 != nil || p2 != nil {
            v = (p1?.val ?? 0)+(p2?.val ?? 0)+carry
            carry =  v/10; v %= 10
            p3?.next = ListNode(v)
            p1 = p1?.next; p2 = p2?.next; p3 = p3?.next
        }
        if carry != 0 { p3?.next = ListNode(carry) }
        return head.next
    }
}

Flatten a Multilevel Doubly Linked List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    func flatten(_ head: Node?) -> Node? {
        getTail(head)
        return head
    }

    private func getTail(_ head: Node?) -> Node? {
        guard let head = head else { return nil }
        if let child = head.child {
            let tail = getTail(child)
            tail?.next = head.next
            head.next?.prev = tail
            head.next = head.child
            head.child?.prev = head
            head.child = nil
        }
        if let p = head.next {
            return getTail(p)
        }
        return head
    }
}

Insert into a Cyclic Sorted List

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
class Solution {
    func insert(_ head: Node?, _ insertVal: Int) -> Node? {
        if head == nil {
            let n = Node(insertVal)
            n.next = n
            return n
        }

        var p = head
        while p != nil {
            if (p!.val <= insertVal &&  p!.next!.val >= insertVal) ||
            (p!.val > p!.next!.val && (insertVal <= p!.next!.val || insertVal >= p!.val ) ||
             p!.next == head
            ) {
                let n = Node(insertVal)
                n.next = p!.next
                p!.next = n
                break
            }
            p = p!.next
        }

        return head
    }
}

Copy List with Random Pointer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    func copyRandomList(_ head: Node?) -> Node? {
        var p = head, nNode = head
        while p != nil {
            let n = Node(p!.val)
            n.next = p?.next
            p?.next = n
            p = p?.next?.next
        }
        p = head
        while p != nil {
            p?.next?.random = p?.random?.next
            p = p?.next?.next
        }
        p = head; nNode = head?.next
        while p != nil {
            let q = p?.next
            p?.next = p?.next?.next
            q?.next = q?.next?.next
            p = p?.next
        }
        return nNode
    }
}

Rotate List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    func rotateRight(_ head: ListNode?, _ k: Int) -> ListNode? {
        var length = 0, fast = head, slow = head, i = 0

        while fast != nil { fast = fast!.next; length += 1 }
        if length < 2 { return head }

        let k = k % length

        fast = head
        while i < k { fast = fast?.next; i += 1 }
        while fast?.next != nil {
            slow = slow?.next; fast = fast?.next
        }

        fast?.next = head
        let node = slow?.next
        slow?.next = nil

        return node
    }
}