24.两两交换链表中的节点
24. 两两交换链表中的节点 - 力扣（LeetCode）
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（只能进行节点交换）。
- 示例 1：
- 输入：head = [1,2,3,4]
- 输出：[2,1,4,3]
- 示例 2：
- 输入：head = []
- 输出：[]
- 示例 3：
- 输入：head = [1]
- 输出：[1]
解题思路：
- 虚拟头：node0、node1=head、node2=head.next、node3=head.next.next
node0->node2, node2->node1, node1->node3; node0=node1, node1=node3 - 递归法：node1=head, node2=head.next, node3=head.next.next
交换node2.next=node1, 递归node1.next=self.swap(node3)
class ListNode():
def __init__(self,val=0,next=None):
self.val=val
self.next=next
class Solution():
def swapPairs(head): # 迭代法
dummy_head = ListNode(next=head)
node0 = dummy_head
node1 = head
while node1 and node1.next:
node2 = node1.next
node3 = node2.next
# 交换
node0.next = node2
node2.next = node1
node1.next = node3
node0 = node1
node1 = node3
return dummy_head.next
def swapPairs(head): # 递归法
if head is None or head.next is None:
return head
node1 = head
node2 = head.next
node3 = head.next.next
node2.next = node1
node1.next = self.swapPairs(node3)
return node2
19.删除链表的倒数第N个节点
19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
-
示例 1：
- 输入：head = [1,2,3,4,5], n = 2
- 输出：[1,2,3,5]
-
示例 2：
- 输入：head = [1], n = 1
- 输出：[]
-
示例 3：
- 输入：head = [1,2], n = 1
- 输出：[1]
解题思路：
- 暴力求解：反转链表 -> 删除第n-1个节点 -> 反转链表
- 双指针：双指针先指向虚拟头节点, 快指针先走n+1步, 双指针同时走, 直到快指针为None, 慢指针.next->慢指针.next.next
class ListNode():
def __init__(val=0,next=None):
self.val=val
self.next=next
class Solution():
def removeNthFromEnd(self,head,n): # 暴力求解法
reverse_head = self.reverse1(head)
current = dummy_head = ListNode(next=reverse_head)
for _ in range(n-1):
current = current.next
current.next = current.next.next
final_head = self.reverse1(dummy_head.next)
return final_head
def reverse1(self,head): # 反转链表方法1
if head is None or head.next is None:
return head
new_head = self.reverse(head.next)
head.next.next = head
head.next = None
return new_head
def reverse2(self,head): # 反转链表方法2
pre = None
cur = head
while cur:
cur.next,pre,cur = pre,cur,cur.next
return pre
def removeNthFromEnd(self,head,n):
if head is None:
return
fast = slow = dummy_head = ListNode(next=head)
for _ in range(n+1):
fast=fast.next
while fast:
slow=slow.next
fast=fast.next
slow.next=slow.next.next
return dummy_head.next
面试题.链表相交
面试题 02.07. 链表相交 - 力扣（LeetCode）
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
- 图示两个链表在节点
c1开始相交：
- 题目数据 保证 整个链式结构中不存在环。
- 注意，函数返回结果后，链表必须 保持其原始结构 。
解题思路：：
若两链表相交，则最后某段必然相同，从短链表起点处开始遍历两链表，必然有相同节点
class ListNode():
def __init__(self,val=val,next=next):
self.val=val
self.next=next
class Solution():
def getIntersectionNode(self,headA,headB):
copyA,copyB,lenA,lenB = headA,headB,0,0
while copyA:
copyA=copyA.next
lenA+=1
while copyB:
copyB=copyB.next
lenB+=1
if lenA<lenB:
lenA,lenB = lenB,lenA
headA,headB = headB,headA
for _ in range(lenA-lenB):
headA=headA.next
while headA and headB:
if headA==headB:
return headA
headA=headA.next
headB=headB.next
return None
142.环形链表Ⅱ
142. 环形链表 II - 力扣（LeetCode）
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。
- 示例 1：
- 输入：head = [3,2,0,-4], pos = 1
- 输出：返回索引为 1 的链表节点
- 解释：链表中有一个环，其尾部连接到第二个节点。
解题思路：
双指针：若有环，①快指针两步，慢指针一步，直到指针相交；②快指针初始化至head，快慢指针依次遍历，直到相交，交点即为入环点。
class ListNode():
def __init__(self,val=val,next=next):
self.val=val
self.next=next
classSolution():
def detectCycle(self,head):
fast,slow=head,head
while fast and fast.next:
fast=fast.next.next
slow=slow.next
if fast==slow:
fast=head
while fast!=slow:
fast=fast.next
slow=slow.next
return fast
return None