# preface

This blog summarizes and arranges the linked list types of sword finger offer, and analyzes the error prone points and forgotten boundary conditions in various topics.

# 1. Print the linked list from end to end

Title Description:
Enter the head node of a linked list and return the value of each node in the order from the end to the head of the linked list (returned with an array).

Example:
Input: {1,2,3}
Return value: [3,2,1]

Idea: create an empty list, traverse the linked list, and insert the values of the linked list into the head of the list in turn.

```class listNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
# Returns a list value sequence from tail to head, for example [1,2,3]
list0 = []
while listNode:
list0.insert(0, listNode.val)
listNode = listNode.next
return list0
```

# 2. The penultimate k nodes in the linked list

Title Description:
Input a linked list and output a linked list. The output linked list contains all nodes from the penultimate node to the tail node in the original linked list.
If the length of the linked list is less than k, please return a linked list with a length of 0.

Example:
Input: {1,2,3,4,5}, 1
Return value: {5}

Idea: create an empty list and store the linked list nodes one by one. Return the penultimate node to return the child linked list after the node.

```class Solution:
def FindKthToTail(self , pHead , k ):
list0 = []
count = 0
count += 1

if count < k or k == 0:
return
else:
return list0[count-k]
```

Title Description:

Example:
Input: {1,2,3}
Return value: {3,2,1}

Idea: three finger acupuncture (PreNode, pHead, nextNode).

```class Solution:
preNode = None
return preNode
```

# 4. Merge two sorted linked lists

Title Description:
Input two monotonically increasing linked lists and output the combined linked list. Of course, we need the combined linked list to meet the monotonic non decreasing rule.

Example:
Input: {1,3,5}, {2,4,6}
Return value: {1,2,3,4,5,6}

Idea: create a new virtual header node with val=0, then compare the two linked lists in turn, and finally return the node after the virtual node (return firstNode.next).

```class Solution:
else:
return firstNode.next
```

# 5. Copy of complex linked list

Title Description:
Enter a complex linked list (each node has a node value and two pointers, one pointing to the next node and the other special pointer random pointing to a random node). Please make a deep copy of this linked list and return the copied head node( Note: please do not return the node reference in the parameter in the output result, otherwise the problem determination program will directly return null). The following figure is a complex linked list with 5 nodes. In the figure, the solid arrow represents the next pointer and the dotted arrow represents the random pointer. For simplicity, the pointer to null is not drawn. Example:
Input: {1,2,3,4,5,3,5, #, 2, #}
Output: {1,2,3,4,5,3,5, #, 2, #}
Analysis: we divide the linked list into two segments. The first half {1,2,3,4,5} is a ListNode, and the second half {3,5, #, 2, #} is a random pointer field representation.
The first half of the above example can represent the listnode of the linked list: 1 - > 2 - > 3 - > 4 - > 5, and the second half, 3, 5, #, 2, # respectively
The position of 1 points to 3, the position of 2 points to 5, the position of 3 points to null, the position of 4 points to 2, and the position of 5 points to null
As shown below: Idea: hash table method.

```class RandomListNode:
def __init__(self, x):
self.label = x
self.next = None
self.random = None

class Solution:
# Return RandomListNode
# write code here
return

dict = {}
# Hash table method. Build a dictionary and create new linked list nodes one by one as value according to the original linked list nodes,
# It corresponds to the original linked list node one by one, and the original linked list node is used as the key

# After the dictionary is created, set the next and random of value according to the next and random points of key
```

# 6. The first common node of two linked lists

Title Description:
Enter two acyclic single linked lists and find their first common node( Note: because the incoming data is a linked list, the prompt of error test data is displayed in other ways to ensure that the incoming data is correct)

Example:
Input: {1,2,3}, {4,5}, {6,7}
Output: {6,7}
Note: the first parameter {1,2,3} represents the non-public part of the first linked list, the second parameter {4,5} represents the non-public part of the second linked list, and the last {6,7} represents the public part of the two linked lists
These three parameters will finally be assembled into two acyclic single linked lists with public nodes in the background

Idea: Double finger acupuncture.

• The first case: there are intersections of the same length
The two pointers go together with the same step size. If they encounter the first same node p1 == p1, exit the loop and return p1.

• The second case: no intersection of the same length
The two pointers go together until they reach the last node. Both p1.next and p2.next are None. If equal conditions are met, exit the loop and return p1.

• The third case: different lengths have intersections
Two pointers go together. When one pointer p1 reaches the end point, it indicates that the linked list where p1 is located is relatively short. Let p1 point to the head node of another linked list and start walking until p2 reaches the end point. Let p2 point to the head node of the short linked list. Then, the length of the next two pointers will be the same, which becomes the first case.

• The fourth case: there is no intersection point in different lengths
Two pointers go together. When one pointer p1 reaches the end point, it indicates that the linked list where p1 is located is relatively short. Let p1 point to the head node of the other linked list and start walking until p2 reaches the end point. Let p2 point to the head node of the short linked list. Then, the length of the next two pointers will be the same, which becomes the second case.

```class Solution:
# double point

# when p1==p2 or p1==p2==None，exit
while p1 != p2:
if not p1:
else:
p1 = p1.next
if not p2:
else:
p2 = p2.next
return p1
```

# 7. The entry node of the link in the linked list

Title Description:
For a linked list, if it contains a ring, please find the entry node of the ring of the linked list. Otherwise, null is returned.

Enter Description:
The input is divided into two segments. The first segment is the linked list before entering the ring, and the second segment is the linked list ring. These two will be assembled into a ring or acyclic single linked list in the background
Return value Description:
Return the entry node of the link of the linked list. And our daemon will print this node

Example 1
Input: {1,2}, {3,4,5}
Return value: 3
Note: return the circular linked list entry node. We will print the circular linked list entry node in the background, that is, 3

Idea:
Hash table method: copy with complex linked list with the help of dictionary

```class Solution:
return
# Hash table: dictionary, copy with complex linked list
dict = {}
else:
return
```

# 8. Delete duplicate nodes in the linked list

Title Description
In a sorted linked list, there are duplicate nodes. Please delete the duplicate nodes in the linked list. The duplicate nodes are not retained and the chain header pointer is returned. For example, the linked list 1 - > 2 - > 3 - > 3 - > 4 - > 4 - > 5 is 1 - > 2 - > 5 after processing

Example
Input: {1,2,3,3,4,4,5}
Return value: {1,2,5}

Idea:
Three finger needling method to find out the repeated node range through cur and nextNode

```class Solution:
# write code here

# Three finger needling method to find out the repeated node range through cur and nextNode

while nextNode:
if cur.val == nextNode.val:
while nextNode and cur.val == nextNode.val:
nextNode = nextNode.next
if nextNode is None:
preNode.next = nextNode
else:
preNode.next = nextNode
cur = nextNode
nextNode = nextNode.next
else:
preNode = preNode.next
cur = cur.next
nextNode = nextNode.next