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 }