SONG Shengjie
To do list: 24. 两两交换链表中的节点，19.删除链表的倒数第N个节点，面试题 02.07. 链表相交，142.环形链表II，总结
24. 两两交换链表中的节点，19.删除链表的倒数第N个节点，面试题 02.07. 链表相交，142.环形链表II，总结
24. 两两交换链表中的节点
Hint: temp can be used to save the temporary 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_head = ListNode (next = head)
current = dummy_head
while current.next != None and current.next.next != None:
temp1 = current.next
temp2 = current.next.next.next
current.next = current.next.next
current.next.next = temp1
temp1.next = temp2
current = current.next.next
return dummy_head.next
19.删除链表的倒数第N个节点
关键点：要删第几个，就要知道它的前一个；快慢指针，快的先走n步，然后再一起走，slow就是倒数第n个
# 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_head = ListNode (next = head)
slow = dummy_head
fast = dummy_head
n += 1
while n :
fast = fast.next
n -= 1
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy_head.next
面试题 02.07. 链表相交
关键点：求两个链表交点节点的指针。要注意，交点不是数值相等，而是指针相等。
步骤：1.求两个链长度；2.求差值；3.长的那条走到等长的点；4.找交点
# 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:
lengthA = lengthB = 0
curA = headA
curB = headB
while curA :
curA = curA.next
lengthA += 1
while curB :
curB = curB.next
lengthB += 1
gap = abs(lengthA - lengthB)
curA = headA
curB = headB
if lengthA > lengthB:
while gap:
curA = curA.next
gap -= 1
else :
while gap:
curB = curB.next
gap -= 1
while curA and curB:
if curA == curB :
return curA
else :
curA = curA.next
curB = curB.next
142.环形链表II
关键点：是否有环、找入口的推导
# 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]:
fast = slow = head
while fast and fast.next :
fast = fast.next.next
slow = slow.next
if fast == slow:
index1 = fast
index2 = head
while index1 != index2:
index1 = index1.next
index2 = index2.next
return index1
return None
总结
-
链表的主要知识：链表的种类主要为：单链表，双链表，循环链表。链表的存储方式：链表的节点在内存中是分散存储的，通过指针连在一起。链表是如何进行增删改查的。数组和链表在不同场景下的性能分析。
-
链表的一大问题就是操作当前节点必须要找前一个节点才能操作。这就造成了，头结点的尴尬，因为头结点没有前一个节点了。每次对应头结点的情况都要单独处理，所以使用虚拟头结点的技巧，就可以解决这个问题。
-
反转链表：迭代法、递归法。
-
结合虚拟头结点和双指针法来移除链表倒数第N个节点。
-
使用双指针来找到两个链表的交点（引用完全相同，即：内存地址完全相同的交点）