The algorithm questions of the linked list are the most common in the interview. Although the questions are simple, they also test the logical thinking and algorithm proficiency of the interviewees. Let's look at their conventional solutions through several common linked list questions! (click the title to go to the original title of leetcode, which is updated from time to time)

1,Determine whether the linked list has a ring

thinking

Use fast and slow pointers to traverse the linked list. The fast pointer takes 2 steps each time and the slow pointer takes 1 step each time. If the two meet, there is a ring, otherwise there is no

package main

import "fmt"

type Node struct {
    Val  int
    Next *Node
}

func hasCycle(head *Node) bool {
    if head != nil {
        fast := head
        slow := head
        for fast != nil && fast.Next != nil {
            fast = fast.Next.Next
            slow = slow.Next
            if fast == slow {
                return true
            }
        }
    }
    return false
}

2,Intermediate node of linked list

thinking

Use fast and slow pointers. The fast pointer takes 2 steps each time, and the slow pointer takes 1 step each time. After the fast pointer has finished, the slow pointer is located at the middle node

func middleNode(head *Node) *Node {
    if head == nil || head.Next == nil {
        return nil
    }
    slow := head
    fast := head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        head.Printf()
    }
    return slow
}

3,Reverse linked list

thinking

Traverse the linked list, point the next pointer of each node to the predecessor node, and the last tail node is the new head node

func (head *Node) reverse() *Node {
    if head == nil {
        return nil
    }
    var preNode *Node
    var newHead *Node
    curNode := head
    for curNode != nil {
        //Save a copy of the back drive node of the current node
        nextNode := curNode.next
        if nextNode == nil {
            newHead = curNode
        }
        //Set the next of the current node as the predecessor node
        curNode.next = preNode
        //Set the predecessor node of the next node as the current node
        preNode = curNode
        //Pointer backward
        curNode = nextNode
    }
    return newHead
}

4,Merge two ordered linked lists

thinking

The double pointer traverses two linked lists respectively, compares the sizes of the two nodes, puts the small ones in the new linked list, and after traversing, points the non traversed parts to the back of the new linked list

func MergeTwoLists(list1 *Node, list2 *Node) *Node {
    //Initialize a virtual head node
    newList := &Node{}
    p := newList
    p1 := list1
    p2 := list2
    //Traverse and compare the size of two pointer values, and stop when one is finished
    for p1 != nil && p2 != nil {
        //Connect the node with a small value to the p pointer
        if p1.Val > p2.Val {
            p.Next = p2
            p2 = p2.Next
        } else {
            p.Next = p1
            p1 = p1.Next
        }
        //p pointer forward
        p = p.Next
    }
    //Put the remaining nodes that are not compared after the p pointer
    if p1 != nil {
        p.Next = p1
    }
    if p2 != nil {
        p.Next = p2
    }
    //The next node that returns the virtual head node is the real head node
    return newList.Next
}

5,Merge K ascending linked lists

thinking

On the basis of merging the two ascending linked lists, you can merge the K linked lists in turn

func mergeKLists(lists []*ListNode) (res *ListNode) {
    for _, v := range lists {
        res = mergeTwoLists(res, v)
    }
    return res
}

//mergeTwoLists() implementation is shown above

6,Split linked list

thinking

Traverse the linked list, divide the node into two linked lists according to the value of the node, and then connect the linked lists together

func partition(head *Node, x int) *Node {
    curNode := head
    //Store the virtual head node of the linked list whose value is less than x
    dummy1 := &Node{}
    //Store the virtual head node of the linked list whose value is greater than or equal to x node
    dummy2 := &Node{}
    p1 := dummy1
    p2 := dummy2
    //Traverse the linked list and divide the original linked list into two
    for curNode != nil {
        if curNode.Val < x {
            p1.Next = curNode
            p1 = p1.Next
        } else {
            p2.Next = curNode
            p2 = p2.Next
        }
        //Disconnect the pointer of the original linked list
        temp := curNode.Next
        curNode.Next = nil
        curNode = temp
    }
    //Connect two linked lists
    p1.Next = dummy2.Next
    return dummy1.Next
}

7,Delete the penultimate node of the linked list

thinking

1. To delete the penultimate node of the linked list, you must first find the penultimate node (n+1)
2. How to find: initialize two double pointers, let p1 go k nodes first, and then let p1 and p2 go together. p1 goes to nil, and the position of p2 is the penultimate node

func removeNthFromEnd(head *Node, n int) *Node {
    //Virtual head node
    p1 := &Node{}
    p1.Next = head
    cur := getKthFromEnd(p1, n+1)
    cur.Next = cur.Next.Next
    return p1.Next
}

//Get the penultimate k-th node in the linked list
func getKthFromEnd(head *Node, k int) *Node {
    p1 := head
    p2 := head
    //Let p1 take k steps first
    for i := 0; i < k; i++ {
        p1 = p1.Next
    }
    for p1 != nil {
        p1 = p1.Next
        p2 = p2.Next
    }
    return p2
}