LeetCode Day 04 Linked list(2/2)
Published:
Today it’s Linked list practice day (2/2).
QUestion 1
Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)
This problem can be solved by setting up a virtual head node.
# 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: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(next = head)
pre = dummy
while pre.next and pre.next.next:
cur = pre.next
post = pre.next.next
# 开始交换cur post
temp = post.next
pre.next = post
post.next = cur
cur.next = temp
pre = pre.next.next
return dummy.next
Question 2
19. Remove Nth Node From End of List
Given the
headof a linked list, remove thenthnode from the end of the list and return its head.
No good ideas. If I want to find the nth from the top it’s ok, but the penultimate n is not well determined.
First, I set up a virtual head node, and then I couldn’t write any more.
I watched the video explanation, the video in order to determine the position of the penultimate n, we use a fast and slow double pointer, first let the fast pointer to move n steps, and then the slow pointer to start moving. When the fast pointer reaches the last position in the chain table, the slow pointer points to the node that needs to be removed. (Wonderful!) But since removing a node requires you to start from the previous bit, the fast pointer has to move n+1 distances first, and then the slow pointer will go again.
# 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: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy_node = ListNode(next=head)
slow ,fast = dummy_node,dummy_node
for _ in range(n):
fast = fast.next
while fast.next != None:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return dummy_node.next
Question 3
160. Intersection of Two Linked Lists
Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.
# 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) -> Optional[ListNode]:
lenA, lenB = 0, 0
cur = headA
while cur:
cur = cur.next
lenA += 1
cur = headB
while cur:
cur = cur.next
lenB += 1
curA, curB = headA, headB
if lenA > lenB:
curA, curB = curB, curA
lenA, lenB = lenB, lenA
for _ in range(lenB - lenA):
curB = curB.next
while curA:
if curA == curB:
return curA
else:
curA = curA.next
curB = curB.next
return None
Question 4
Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.
Do not modify the linked list.
Using the fast and slow pointers to determine if there exists a cycle
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
p = head
q = slow
while p!=q:
p = p.next
q = q.next
return p
return None