LeetCode Linked List

Posted on Edited on Disqus: Word count in article: 9.5k Reading time ≈ 9 mins.

Design Linked List

This is the solution for the “Design Linked List” problem on LeetCode. It creates a class called MyLinkedList which implements the functionality of a 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
72
73
74
75
76
77
78
79
80
81
82
83
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
        }
    }

    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
        }
    }

    private func findNode(_ index: Int) -> Node? {
        var p: Node?
        var 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
        var i: Int = 0
        while p != nil, i < count {
            print(p!.val, terminator: "->" )
            p = p?.next
            i += 1
        }
        print("")
    }
}

Linked List Cycle

This is the solution for the “Linked List Cycle” problem on LeetCode. It contains a class called Solution which checks whether a linked list contains a cycle.

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

Linked List Cycle II

This is the solution for the “Linked List Cycle II” problem on LeetCode. It contains a class called Solution which finds the node where the cycle begins in a linked list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    func detectCycle(_ head: ListNode?) -> ListNode? {
        var slow = head
        var 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

This is the solution for the “Intersection of Two Linked Lists” problem on LeetCode. It contains a class called Solution which finds the intersection node 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
28
29
30
31
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
        var 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

This is the solution for the “Remove Nth Node From End of List” problem on LeetCode. It contains a class called Solution which removes the nth node from the end of a 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 removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        var pHead = ListNode(-1, head)
        var p0: ListNode? = pHead
        var p1 = p0
        var i = 0
        var 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

This is the solution for the “Reverse Linked List” problem on LeetCode. It contains a class called Solution which reverses a 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
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
        var cur = head
        while cur != nil {
            let p = cur?.next
            cur?.next = prev
            prev = cur
            cur = p
        }
        return prev
    }
}

Remove Linked List Elements

This is the solution for the “Remove Linked List Elements” problem on LeetCode. It contains a class called Solution which removes all elements of a linked list that have a certain value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

This is the solution for the “Odd Even Linked List” problem on LeetCode. It contains a class called Solution which rearranges a linked list such that all the odd nodes come before the even nodes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    func oddEvenList(_ head: ListNode?) -> ListNode? {
        let evenHead = head
        let oddHead = head?.next
        var evenP = evenHead
        var 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

This is the solution for the “Palindrome Linked List” problem on LeetCode. It contains a class called Solution which checks whether a linked list is a palindrome.

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
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
        var 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
        var 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
        var cur = head
        while cur != nil {
            let p = cur?.next
            cur?.next = prev
            prev = cur
            cur = p
        }
        return prev
    }
}

Merge Two Sorted Lists

This is the solution for the “Merge Two Sorted Lists” problem on LeetCode. It contains a class called Solution which merges two sorted linked lists into a single sorted linked list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

This is the solution for the “Add Two Numbers” problem on LeetCode. It contains a class called Solution which adds two numbers represented as 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
class Solution {
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        let head = ListNode(-1)
        var p1 = l1
        var p2 = l2
        var p3: ListNode? = head
        var v = 0
        var 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

This is the solution for the “Flatten a Multilevel Doubly Linked List” problem on LeetCode. It contains a class called Solution which flattens 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
23
24
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

This is the solution for the “Insert into a Cyclic Sorted List” problem on LeetCode. It contains a class called Solution which inserts a node 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

This is the solution for the “Copy List with Random Pointer” problem on LeetCode. It contains a class called Solution which creates a deep copy of a linked list with random pointers.

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
class Solution {
    func copyRandomList(_ head: Node?) -> Node? {
        var p = head
        var 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

This is the solution for the “Rotate List” problem on LeetCode. It contains a class called Solution which rotates a linked list to the right by k places.

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 rotateRight(_ head: ListNode?, _ k: Int) -> ListNode? {
        var length = 0
        var fast = head
        var slow = head
        var 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
    }
}

Translated by gpt-3.5-turbo