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]
def printListFromTailToHead(self, listNode):
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
while pHead:
list0.append(pHead)
pHead = pHead.next
count += 1
if count < k or k == 0:
return
else:
return list0[count-k]
3. Reverse linked list
Title Description:
Enter a linked list. After reversing the linked list, output the header of the new linked list.
Example:
Input: {1,2,3}
Return value: {3,2,1}
Idea: three finger acupuncture (PreNode, pHead, nextNode).
class Solution:
# Return to ListNode
def ReverseList(self, pHead):
preNode = None
while pHead:
nextNode = pHead.next
pHead.next = preNode
preNode, pHead = pHead, nextNode
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:
# Return to merged list
def Merge(self, pHead1, pHead2):
firstNode = head0 = ListNode(0)
while pHead1 and pHead2:
if pHead1.val <= pHead2.val:
head0.next = pHead1
pHead1 = pHead1.next
else:
head0.next = pHead2
pHead2 = pHead2.next
head0 = head0.next
if pHead1 is None:
head0.next = pHead2
if pHead2 is None:
head0.next = pHead1
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
def Clone(self, pHead):
# write code here
if pHead is None:
return
dict = {}
head = pHead
# 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
while head:
dict[head] = RandomListNode(head.label)
head = head.next
# After the dictionary is created, set the next and random of value according to the next and random points of key
head = pHead
while head:
dict[head].next = dict.get(head.next)
dict[head].random = dict.get(head.random)
head = head.next
return dict[pHead]
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:
def FindFirstCommonNode(self, pHead1, pHead2):
# double point
p1 = pHead1
p2 = pHead2
# when p1==p2 or p1==p2==None，exit
while p1 != p2:
if not p1:
p1 = pHead2
else:
p1 = p1.next
if not p2:
p2 = pHead1
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:
def EntryNodeOfLoop(self, pHead):
if pHead is None:
return
# Hash table: dictionary, copy with complex linked list
dict = {}
while pHead:
if dict.get(pHead):
return pHead
else:
dict[pHead] = pHead.val
pHead = pHead.next
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:
def deleteDuplication(self, pHead):
# write code here
if pHead is None:
return pHead
if pHead.next is None:
return pHead
preNode = head = ListNode(0)
# Three finger needling method to find out the repeated node range through cur and nextNode
preNode.next = pHead
cur = pHead
nextNode = pHead.next
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
return head.next