Interview essential leetcode linked list algorithm question summary, whole process dry goods!

introduction ：

The difficulty of collecting questions is at the simple level and intermediate level , It is also a common topic in interviews . Problem solving , The development language used is Swift.

   Because the description of the topic is very long , And there are various case tips , In order not to occupy space , So it didn't show , You can check the description of the topic directly through the question number query .

   The writing order of the article is ：

1. Show the title number and the link to the title

2. The core idea

3. Code implementation .

Finally, the code provided in this article is in LeetCode Mention the traffic .

1. Linked List Questions（ Linked list related problems ）

1.LeetCode_141: Is there a link in the list 2.LeetCode_160: Intersecting list 3.LeetCode_206: List reversal 4.LeetCode_ 21: Merge two ordered lists 5. The finger of the sword offer_ 22: Last in the list k Nodes 6. The finger of the sword Offer_ 06: Print linked list from end to end 7.LeetCode_ 19: Delete the last of the linked list N Nodes 8.LeetCode_237: Delete the nodes in the list 9.LeetCode_ 83: Delete duplicate elements from the sort list 10.LeetCode_ 82: Delete all duplicate elements in the sorting linked list II 11.LeetCode_203: Delete all nodes of a value in the linked list 12.LeetCode_ 86: Separate the list 13.LeetCode_328: Odd and even list

1. Is there a link in the list

1.1 Explain the core idea

This idea uses the speed pointer . analogy ： Like the school playground ,A、B They ran around the playground ,A Slow running ,B Run fast , After they started running , as time goes on , Eventually they will meet somewhere on the playground .    If A、B Running on a highway , One slow, one fast , They never had a chance to meet .    The speed pointer uses the above principle ,slow The pointer goes one step at a time ,quick The pointer takes two steps at a time . Traverse the entire linked list in this way . If you don't meet, there is no ring , It's like a highway . If we meet each other , Description ring , Like the circular track on the school playground .

1.2 Code implementation

func hasCycle(_ head: ListNode?) -> Bool {
    if head == nil || head?.next == nil { return false }
    var slow = head
    var fast = head?.next

    while fast != nil && fast?.next != nil {
        if slow === fast { return true }
        slow = slow?.next
        fast = fast?.next?.next
    }

    return false
}

Copy

2. The list intersects

2.1 Explain the core idea

You become me , I become you , We met . Then why can we meet ？ Set long linked list A The length is LA, Short list length LB; Because of the same speed , Then in the long linked list A Walk the LA Length , Short linked list B Have turned their heads in A Let's go LA-LB The length of , The remaining length to go is LA-(LA-LB) = LB; Then long linked list A Turn your head around B Go up , The remaining length to go is also LB; That is to say, there are currently two linked lists “ alignment ” 了 . therefore , The next same node is the intersection of the two linked lists . What if there is no intersection between the two linked lists ？ answer ： In that case, No 4 Step will be executed until the end of the two linked lists ,la,lb All for null, It's going to jump out of the loop , return null.

2.2 Code implementation

func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
        var currentA = headA
        var currentB = headB
        //  !==  Using the opposite image is not equal to   No  !=
        while currentA !== currentB {
        currentA = (currentA != nil) ? currentA?.next : headB
        currentB = (currentB != nil) ? currentB?.next : headA
      }
        return currentA
    }

Copy

3. List reversal

3.1 Explanation of problem-solving methods

Set up three nodes pre、cur、next （1） Every time you check cur Whether the node is NULL, If it is , End cycle , Get the results （2） If cur The node is not NULL, Then set the temporary variable first next by cur The next node of （3） Give Way cur The next node of becomes a point pre, Then pre Move cur,cur Move to next （4） repeat （1）（2）（3） （5） return pre）

3.2 Code implementation

func reverseList(_ head: ListNode?) -> ListNode? {
    var pre: ListNode?
    var cur = head
    var next = head?.next
    while cur != nil {
        next = cur?.next
        cur?.next = pre //  reverse ,  Point to pre
        pre = cur
        cur = next
    }
    return pre
}

Copy

4. Merge two ordered lists

4.1 The core idea of algorithm

Because it's hard to judge at first l1 and l2 Who is the empty node , So create dummy This empty node ; Through the nodes of two linked lists val Size contrast , Update empty list pointer cur value Each update cur After value , Update the pointers of two ordered linked lists at the same time , Save linked list pointer cur To the latest location Last return To dummy.next, That is, the head node can get the whole linked list

4.2 Code implementation

func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    if l1 == nil { return l2 }
    if l2 == nil { return l1 }
    //  Create an empty node , And let cur The pointer points to it , It provides convenience for the final return result , It's a good skill 
    var dummy = ListNode()
    var cur: ListNode? = dummy
    var headA = l1
    var headB = l2

    while headA != nil && headB != nil {
        if headA!.val < headB!.val {
            cur?.next = headA
            headA = headA?.next
        } else {
            cur?.next = headB
            headB = headB?.next
        }
        cur = cur?.next
    }

    if headA == nil {
        cur?.next = headB
    }

    if headB == nil {
        cur?.next = headA
    }
    return dummy.next
}

Copy

5. Last in the list k Nodes

5.1 The core idea

Double pointer l r r Pointer first k-1 Step , such l Pointers and r The difference between the pointers k-1. This is the time l and r Go back together , When r Go to the end of the list ,l The pointer is just the penultimate k Nodes

5.2 Code implementation

func getKthFromEnd(_ head: ListNode?, _ k: Int) -> ListNode? {
    if head == nil || k == 0 { return head }
    var count = k
    var l: ListNode? = head
    var r: ListNode? = head
    while count > 1 {
        guard let node = r?.next else { return nil }
        count -= 1
        r = node
    }
    while r?.next != nil {
        l = l?.next
        r = r?.next
    }
    
    return l
}

Copy

6. Print the linked list in reverse order

6.1 The core idea

Since the reverse order , Then use recursion

6.2 Code implementation

var nums = [Int]()
func reversePrint(_ head: ListNode?) -> [Int] {
    if head == nil { return nums }
    reverse(head)
    nums.append(head!.val)
    return nums
}

func reverse(_ head: ListNode?) {
    guard let next = head?.next else { return }
    reverse(head?.next)
    nums.append(next.val)
}

Copy

Or so ：

var nums = [Int]()
func reversePrint(_ head: ListNode?) -> [Int] {
    guard let head = head else {
        return []
    }
    reversePrint(head.next)
    nums.append(head.val)
    return nums
}

Copy

7. Delete the last of the linked list N Nodes

7.1 The core idea

This topic is similar to 5 The idea of the question is the same . But there is a very special case ： Suppose the length of the linked list is N, Delete the last N The first node is the head node . In order to deal with this special situation , We can start from 4 Get inspiration from the question , Is to create a virtual empty node dummy, And let dummy.next = head that will do .

7.2 Code implementation

func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
    if head == nil || n == 0 { return nil }
    var count = n
    var dummy = ListNode(0,head)
    var first: ListNode? = dummy
    var second: ListNode? = dummy
    
    while count > 0 {
        guard let node = second?.next else { return nil }
        second = node
        count -= 1
    }
    
    while second?.next != nil  {
        second = second?.next
        first = first?.next
    }
    first?.next = first?.next?.next
    return dummy.next
}

Copy

8. Delete the nodes in the list

8.1 The core idea

Thought analysis If we want to delete a node in the list , The general operation is ： Modify the pointer of the previous node of the node to be deleted Point the pointer to the next node that you want to delete for example , Linked list [4, 5, 1, 9] in , When we want to delete nodes 5 when , We will modify the nodes 5 Last node 4 The pointer to , Let it point to the node 5 The next node of , That is node 1. But this problem only tells us the nodes to be deleted , We don't know what the previous node of this node is , What should I do at this time ？ Since we need to know the last node when we want to delete a node , If we don't know the last node , Let's find a node that can know the previous node , Make it the node to delete , Then delete it . It sounds like a bit of a mouthful ？ Don't worry , Let's look at an example ！ still [4, 5, 1, 9] Linked list , Or delete the node 5. First , We put the nodes 5 The value of the next node is assigned to it , The node becomes [4, 1, 1, 9] Then delete the third node 1 that will do

8.2 Code implementation

func deleteNode(_ node: ListNode?) {
    guard let node = node else { return }
    var nextNode = node.next
    node.val = nextNode!.val
    node.next = nextNode!.next
}

Copy

9. Delete duplicate elements from the sort list

9.1 The core idea

Appoint cur The pointer points to the head head When cur and cur.next The existence of is the end of the loop condition , When one of the two does not exist, it means that there is no need to repeat the linked list When cur.val and cur.next.val When equal, it means that the weight needs to be removed , Will cur The next pointer of points to the next , In this way, we can achieve the effect of de repetition If not, then cur Move to the next position and continue the cycle

Solution 2 ：

There's another solution ： Inspiration comes from 2 The arithmetic problem of the sum of numbers , Use map The thought of weight removal .

9.2 Code implementation

 func deleteDuplicates(_ head: ListNode?) -> ListNode? {
        if head == nil {  return nil }
        var cur = head
        while cur != nil && cur?.next != nil {
            if cur!.val == cur!.next!.val {
                cur?.next = cur?.next?.next
            } else {
                cur = cur?.next
            }
        }
        return head
    }

Copy

    func removeDuplicateNodes(_ head: ListNode?) -> ListNode? {
        if head == nil { return nil }
        var map:[Int: ListNode] = [:]
        var p = head
        map[p!.val] = p!
        while p?.next != nil {
            if map[p!.next!.val] != nil {
                p!.next = p!.next!.next
            } else {
                map[p!.next!.val] = p!.next!
                p = p?.next
            }
        }
        return head
    }

Copy

10. Delete all duplicate elements in the sorting linked list II

10.1 The core idea

Because the given linked list is in good order , Therefore, the position of repeated elements in the linked list is continuous , Therefore, we only need to traverse the linked list once , You can delete duplicate elements . Because the head node of the linked list may be deleted , So we need to use an extra dummy node （dummy node） Point to the head node of the list . In particular , We start with the pointer cur Point to the dummy node of the linked list , Then start traversing the linked list . If at present cur.next And cur.next.next The corresponding elements are the same , So we're going to have to cur.next And all linked list nodes with the same element value are deleted . Let's write down the value of this element x, Then continue to cur.next Remove from list , until cur.next Null node or its element value is not equal to x until . here , We set the values of all elements in the linked list to x Delete all nodes . If at present cur.next And cur.next.next The corresponding elements are different , Then it means that only one element in the linked list has a value of cur.next The node of , So we can put cur Point to cur.next. After traversing the entire linked list , We return the next node of the dummy node of the linked list dummy.next that will do .

10.2 Code implementation

func deleteDuplicates(_ head: ListNode?) -> ListNode? {
        if head == nil { return nil }
        var dummy = ListNode(0,head)
        var cur: ListNode? = dummy
        while cur?.next != nil && cur?.next?.next != nil {
            if cur!.next!.val == cur!.next!.next!.val {
                let x = cur!.next!.val
                //  secondary  while  Delete duplicate nodes 
                while cur?.next != nil && cur!.next!.val == x {
                    cur?.next = cur?.next?.next
                }
            } else {
               cur = cur?.next
            }
        }
        return dummy.next
    }

Copy

11. Delete all nodes of a value in the linked list

11.1 The core idea

Because the worry node is also a deleted node , So add one at the beginning dummy Virtual node . The next step is to delete . especially cur?.next = cur?.next?.next // Execution deletion this sentence , Just keep deleting , Until the next node value is not equal to val, Just let cur = cur?.next

11.2 Code implementation

 func removeElements(_ head: ListNode?, _ val: Int) -> ListNode? {
        if head == nil { return head }
        var dummy = ListNode(0, head)
        var cur: ListNode? = dummy
        while cur?.next != nil {
            if cur!.next!.val == val {
                cur?.next = cur?.next?.next //  Execution deletion 
            }else {
                cur = cur?.next
            }
        }
        return dummy.next
    }

Copy

12. Split the list

12.1 The core idea

2 Create a new linked list to save , Finally, put two more 2 Just link the linked list

12.2 Code implementation

func partition(_ head: ListNode?, _ x: Int) -> ListNode? {
    if head == nil { return nil }
    var node = head
    var lHead = ListNode(0), lTrail = lHead
    var rHead = ListNode(0), rTrail = rHead
    while node != nil {
        if node!.val < x {
            lTrail.next = node
            lTrail = lTrail.next! //lTrail = curHead!
        }else {
            rTrail.next = node
            rTrail = rTrail.next! //  rTrail = curHead!
        }
        node = node?.next
    }
    rTrail.next = nil
    lTrail.next = rHead.next
    return lHead.next
}

Copy

13. Odd and even list

13.1 The core idea

and 12 The solution of the problem is the same , Just change the judgment conditions

13.2 Code implementation

 func oddEvenList(_ head: ListNode?) -> ListNode? {
        if head == nil { return nil }
        var node = head
        var lHead = ListNode(0), lTrail = lHead
        var rHead = ListNode(0), rTrail = rHead
        var flag = false
        while node != nil {
            if !flag {
                lTrail.next = node
                lTrail = lTrail.next!
            }else {
                rTrail.next = node
                rTrail = rTrail.next! //  rTrail = curHead!
            }
            flag.toggle()
            node = node?.next
        }
        rTrail.next = nil
        lTrail.next = rHead.next
        return lHead.next
    }

Copy

end