Sword finger offer -- linked list (python)

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

Keywords: Python linked list

Added by 9mm on Mon, 06 Sep 2021 05:11:00 +0300