题目简介
24. 两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
19.删除链表的倒数第N个节点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
面试题 02.07. 链表相交
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
142.环形链表II
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
初见思路
# 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]:
if not head or not head.next: ## edge case
return head
dummy = ListNode(-1,head)
pre,cur = dummy,dummy.next
while pre.next and pre.next.next:
mid = pre.next
last = pre.next.next
mid.next = last.next
last.next = mid
pre.next = last
pre = mid
return dummy.next
# 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]:
size, cur = 0, head
while cur:
size += 1
cur = cur.next
if n == size:
return head.next
dummy = ListNode(-1,head)
i,size = 0,size - n
pre, cur = dummy, dummy.next
while cur:
if i == size:
pre.next = cur.next
break
pre = pre.next
cur = cur.next
i += 1
return dummy.next
面试题 02.07. 链表相交
# 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:
a,b = headA, headB
while a != b:
a = a.next if a else headB
b = b.next if b else headA
return a
# 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 True:
if not(fast and fast.next): return None # stop condition
slow = slow.next
fast = fast.next.next
if slow == fast: break
fast = head
while slow != fast:
slow,fast = slow.next, fast.next
return slow
复盘思路
https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html
重点难点
- 环形链表的检测
- 链表节点的复杂互换
- 链表基本操作的复盘
今日收获
(待复盘总结)
