Leetcode - linked list

One 、 Remove linked list elements

Answer key

In fact, this problem only needs to traverse the linked list , It should be noted that , When doing this topic , It is best to create a new header node , Otherwise, it is difficult to delete . Deletion is the most basic operation in the linked list , Need to master .

Code

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        dummy = ListNode(None)# Create a new virtual head node 
        dummy.next = head
        cur = dummy
    
        while cur.next:
            if cur.next.val==val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return dummy.next

Two 、 Reverse a linked list

Answer key

For students who have just learned data structure , If you flip the linked list , The first idea may be head insertion , This method is also easier to implement , Here we give two solutions of double pointer and recursion .

Code

Double pointer

# Double pointer 
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        cur = head   
        pre = None
        while(cur!=None):
            temp = cur.next #  Save it  cur The next node of , Because the next thing to change cur->next
            cur.next = pre # reverse 
            # to update pre、cur The pointer 
            pre = cur
            cur = temp
        return pre

recursive
In fact, this recursion is roughly the same as the double pointer solution , Understand the double pointer , Recursion is also easy to implement

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        
        def reverse(pre,cur):
            if not cur:
                return pre
                
            tmp = cur.next
            cur.next = pre

            return reverse(cur,tmp)
        
        return reverse(None,head)

Recursive two

def reverseList(self, head: ListNode) -> ListNode:
    if head is None or head.next is None:
        return head
    
    p = self.reverseList(head.next)
    head.next.next = head
    head.next = None

    return p

3、 ... and 、 Two or two exchange nodes in a linked list

Answer key

Create a new virtual head node dummy, Three nodes are a group , Draw a picture to clarify the logic , Be sure to remember before breaking the chain , Point to the next node with a pointer .

Code

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if head is None:
            return None
        if head.next is None:
            return head

        dummy = ListNode(None)
        dummy.next = head
        cur = dummy
        while cur.next and cur.next.next:
            tmp1 = cur.next # Record temporary nodes 
            tmp2 = cur.next.next.next # Record temporary nodes 

            cur.next = cur.next.next # Step one 
            cur.next.next = tmp1 # Step two 
            cur.next.next.next = tmp2 # Step three 

            cur = cur.next.next
        
        return dummy.next

Four 、 Delete the last of the linked list N Nodes

Answer key

Use double pointers to solve this problem , Set two pointers ,slow,fast, First, let fast go N Step , Then the two pointers move together again , When fast When moving to the last node ,slow The pointer is on the penultimate N Nodes .

Code

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(None)
        dummy.next = head
        slow,fast = dummy,dummy
        while n!=0:
            fast = fast.next
            n -= 1
        while fast.next != None:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy.next

In fact, there is also a violent solution to this problem , Last but not least k The first node is actually the positive number len(head)-k+1 Nodes , It should be noted that len Functions do not come with , You need to define

5、 ... and 、 Intersecting list

Answer key

Use double pointer , To ensure that the two linked lists reach the last node at the same time , First calculate the length difference between the two linked lists dist,long The pointer points to the long linked list ,short Point to a short linked list , And let it go first long go dist Step , Then move synchronously . When long==short When , It means that a public node is encountered .

Code

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        # Return when one is empty Null
        if headA is None or headB is None:
            return None
        # adopt while Cycle to get the length of each linked list 
        curA = headA
        curB = headB
        lengthA,lengthB = 0,0
        while curA != None:
            curA = curA.next
            lengthA += 1
        while curB != None:
            curB = curB.next
            lengthB += 1
        # take long The pointer points to the long one 
        if lengthA > lengthB:
            dist = lengthA-lengthB
            long = headA
            short= headB
        else:
            dist = lengthB-lengthA
            long = headB
            short = headA
        # Let the long go first dist Step 
        while dist != 0:
            long = long.next
            dist -= 1
        # If long and short meet , It means that a public node is encountered 
        while long != None and short != None:
            if long == short:
                return long
            long = long.next
            short = short.next
        return None

6、 ... and 、 Circular list

Answer key

You can use the fast and slow pointer method , Defining the fast and slow The pointer , Start from the beginning ,fast The pointer moves two nodes at a time ,slow The pointer moves one node at a time , If fast and slow The hands meet on the way , It shows that the list has links .

Why? fast Take two nodes ,slow Take a node , If there is a ring , It's bound to meet in the ring , Instead of always staggering

First and foremost ：fast The pointer must enter the ring first , If fast Pointers and slow If the pointer meets , Must have met in the ring , There is no doubt that .

This is because fast It's two steps ,slow It's a step , In fact, compared with slow Come on ,fast Is the proximity of a node to a node slow Of , therefore fast Must be able to communicate with slow coincidence .

You can draw the whole process by yourself , Can better understand logic

Code

'''  Speed pointer , As long as there is a ring , Two pointers must meet  '''
class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if head is None:
            return False
        
        slow,fast = head,head
        while fast!=None:
            fast = fast.next
            if fast != None:
                fast = fast.next
            if fast==slow:
                return True
            slow = slow.next
        
        return False

7、 ... and 、 Circular list ||

Answer key

Suppose from the head node to the ring entry node The number of nodes of is x. Ring entry node to fast The pointer and slow The pointer meets the node The number of nodes is y. From the meeting node And then to the ring entrance node, the number of nodes is z. As shown in the figure ：

So when we meet ： slow The number of nodes passed by the pointer is : x + y, fast Number of nodes passed by the pointer ：x + y + n (y + z),n by fast The pointer went inside the ring n Just met slow The pointer , （y+z） by Number of nodes in a circle A.

because fast The pointer is to walk two nodes in one step ,slow The pointer goes one node at a time , therefore fast Number of nodes passed by the pointer = slow Number of nodes passed by the pointer * 2：

(x + y) * 2 = x + y + n (y + z)

Eliminate one on both sides （x+y）: x + y = n (y + z)

Because you're looking for a circular entrance , So what is required is x, because x Express Head node to The distance of the ring entrance node .

So ask for x , take x Put it alone on the left ：x = n (y + z) - y ,

Again from n(y+z) To propose one （y+z） Come on , After sorting out the formula, it is the following formula ：x = (n - 1) (y + z) + z Note that there n Must be greater than or equal to 1 Of , because fast The pointer must go at least one more circle to meet slow The pointer .
First take n by 1 For example , signify fast After the pointer makes a circle in the ring , I met slow The pointer is broken .

When n by 1 When , The formula is reduced to x = z,

That means , Start a pointer from the beginning node , From the meeting node Also start a pointer , These two pointers walk only one node at a time , So when these two pointers meet, it is The node of the ring entrance .

That is, at the meeting node , Define a pointer index1, Set a pointer at the head node index2.

Give Way index1 and index2 Move at the same time , Move one node at a time , Then the place where they met was The node of the ring entrance .
that n If it is greater than 1 What's the situation , Namely fast The pointer turns in a circle n After the circle, I met slow The pointer .

In fact, this situation is similar to n by 1 When The effect is the same , The same can be found in this way Circular entry node , It's just ,index1 The pointer is in the ring Turn more (n-1) circle , Then meet again index2, The meeting point is still the entrance node of the ring .

The above solution comes from the code Capriccio Carla The big guy's question , I felt very clear and moved here

Code

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if head is None:
            return None
        slow,fast = head,head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow==fast: # Meeting means meeting a ring 
                index1 = head
                index2 = fast
                while index1!=index2:
                    index1 = index1.next
                    index2 = index2.next
                return index2
        return None