# Gorang version of high-frequency algorithm of linked list (clear thinking and detailed comments)

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
}

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 {
return nil
}
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}```

### 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 {
return nil
}
var preNode *Node
for curNode != nil {
//Save a copy of the back drive node of the current node
nextNode := curNode.next
if nextNode == nil {
}
//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
}
}```

## 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 {
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
```

### 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 {
//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
}
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 {
p1 := &Node{}
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 {