task for today
1. 24. 两两交换链表中的节点
2. 19.删除链表的倒数第N个节点
3. 面试题 02.07. 链表相交
4. 142.环形链表II
-------------------------------------------------------------------
1. 24. 两两交换链表中的节点
In this practice, pay attention to following several key points:
(1) dummy point is still recommended;
(2) the condition for while loop to execute the swap operation;
(3) node at odd position should be reserved as "temp=cur.next" and "temp1=cur.next.next.next" for avoiding being modified;
(4) the special circumstances of none head or single node
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
# special cases
if not head or not head.next:
return head
# create dummy node
dummy_node = ListNode(next=head)
cur = dummy_node
# the condition for while loop
while cur.next and cur.next.next:
# reserve odd position node
temp = cur.next
temp1 = cur.next.next.next
cur.next = cur.next.next
cur.next.next = temp
temp.next = temp1
cur = cur.next.next
return dummy_node.nextHere are the corresponding version for Go
func swapPairs(head *ListNode) *ListNode {
// special circumstance
if head == nil || head.Next == nil {
return head
}
// dummmy node
dummy_node := &ListNode{}
dummy_node.Next = head
cur := dummy_node
// condition for while loop
for cur.Next != nil && cur.Next.Next != nil {
temp := cur.Next
temp1 := cur.Next.Next.Next
cur.Next = cur.Next.Next
cur.Next.Next = temp
temp.Next = temp1
cur = cur.Next.Next
}
return dummy_node.Next
}Use Rust to code linked list related practice is too disgusting, so I skip rust in linked list part ;-|
2. 19.删除链表的倒数第N个节点
In this practice, it is more desirable to finish it just within once going-through. Therefore, double pointer mindset should be recalled. Following points should be paid attention to.
(1) dummy node is still needed;
(2) slow and fast both start from dummy node
(3) fast should firsly go (n+1) step, which is more convinent as the slow would stop at the node in front of the node penidng to be deleted.
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
# dummy node
dummy_node = ListNode(next=head)
slow = dummy_node
fast = dummy_node
# start to move fast for n+1 steps
for i in range(n + 1):
fast = fast.next
# start to simultaneously move fast and slow
while fast:
slow = slow.next
fast = fast.next
# do the deleting
slow.next = slow.next.next
return dummy_node.nextGo version
func removeNthFromEnd(head *ListNode, n int) *ListNode {
// dummy node
dummy_node := &ListNode{}
dummy_node.Next = head
slow := dummy_node
fast := dummy_node
// move fast for n+1 steps
for i := 0; i < n+1; i++ {
fast = fast.Next
}
// move slow and fast simultaneously until fast point to None
for fast != nil {
slow = slow.Next
fast = fast.Next
}
// do the deleting
slow.Next = slow.Next.Next
return dummy_node.Next
}3. 面试题 02.07. 链表相交
In this practice, the key point is to find the difference of the two linked list's length, here are the key steps:
(1) find each length
(2) calculate the difference
(3) move the longer pointer to align with the shorter pointer
(4) move together to find the intersection
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
# derive the length for two linked list
lenA, lenB = 0, 0
curA, curB = headA, headB
while curA:
curA = curA.next
lenA += 1
while curB:
curB = curB.next
lenB += 1
# move the longer one first to align with the shorter one
if lenA > lenB:
diff = lenA - lenB
curA = headA
curB = headB
for i in range(diff):
curA = curA.next
else:
diff = lenB - lenA
curA = headA
curB = headB
for i in range(diff):
curB = curB.next
# move together to find the intersection node
while curA != curB:
curA = curA.next
curB = curB.next
return curAGO verion
func getIntersectionNode(headA, headB *ListNode) *ListNode {
// find length
lenA := 0
lenB := 0
curA := headA
curB := headB
for curA != nil {
curA = curA.Next
lenA += 1
}
for curB != nil {
curB = curB.Next
lenB += 1
}
if lenA > lenB {
diff := lenA - lenB
curA = headA
curB = headB
for i := 0; i < diff; i++ {
curA = curA.Next
}
} else {
diff := lenB - lenA
curA = headA
curB = headB
for i := 0; i < diff; i++ {
curB = curB.Next
}
}
for curA != curB {
curA = curA.Next
curB = curB.Next
}
return curA
}4. 142.环形链表II
In this practice, three key points need to be clear:
(1) decide whether there is a circle, use fast and slow pointer, if they meet, then there must be a circle;
(2) since they will meet within the circle, which will be position: let the line part is x, length between meetup point and entrance of the circle is y, "the other way around" length is z, which makes the circle circumvent is (y + z);
when they meet, the distance of fast should be twice as that of short one, which gives: (x + y) * 2 = x + y + (y + z) * n, where n represents the circles that fast pointer have finished before meeting slow pointer.
this equation gives results: x = z + (n - 1)*(y + z), this represent the line part equals to the z, as (n - 1)*(y + z) represents the circles which can be offset
(3) based on (2), set two pointers, respectively starting from head and meetup node, both with speed 1 node/setp, they will meet at the entrance node of the circle.
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = head
fast = head
# move fast and slow
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# meet up
if slow == fast:
# move one to head
slow = head
# move at same speed
while slow != fast:
slow = slow.next
fast = fast.next
# meet node will be the entrance of circle
return slow
# no circle return
return NoneGo version
func detectCycle(head *ListNode) *ListNode {
slow := head
fast := head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
slow = head
for slow != fast {
slow = slow.Next
fast = fast.Next
}
return slow
}
}
return nil
}