24：两两交换链表中的节点
链接：24. 两两交换链表中的节点 - 力扣（LeetCode）
虚拟头节点
# 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: return head
dummpy=ListNode(next=head)
left,cur=dummpy,head
while cur and cur.next:
right=cur.next
tmp=right.next
left.next=right
right.next=cur
cur.next=tmp
left=cur
cur=cur.next
return dummpy.next
swapPairs
19:删除链表的倒数第n个节点
链接：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
# 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]:
if not head: return head
dummpy=ListNode(next=head)
cur=dummpy.next
lens=0
while cur:
cur=cur.next
lens+=1
cur=dummpy
for i in range(lens-n): cur=cur.next
if(cur.next): cur.next=cur.next.next
return dummpy.next
removeNthFromEnd
链表相交
链接：面试题 02.07. 链表相交 - 力扣（LeetCode）
# 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:
lenA,lenB=self.get_len(headA),self.get_len(headB)
if(lenA>lenB):
for i in range(lenA-lenB): headA=headA.next
else:
for i in range(lenB-lenA): headB=headB.next
while headA:
if(headA==headB): return headA
headA=headA.next
headB=headB.next
return None
def get_len(self,head):
lens=0
while head:
lens+=1
head=head.next
return lens
getIntersectionNode
142:环形链表II
链接：142. 环形链表 II - 力扣（LeetCode）
快指针一次走两步，慢指针一次走一步，快=慢，有环：慢指针从头开始走，快指针一次走一步，快=慢，环入口
# 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]:
if(not head): return head
fast,slow=head,head
while fast and fast.next:
fast=fast.next.next
slow=slow.next
if fast==slow:
slow=head
while slow!=fast:
slow=slow.next
fast=fast.next
return slow
return None
detectCycle
2:两数相加
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
cur1,cur2=l1,l2
head=ListNode()
re,cur=head,head
num=0
while cur1 or cur2:
if(cur1):
c1=cur1.val
cur1=cur1.next
else: c1=0
if(cur2):
c2=cur2.val
cur2=cur2.next
else: c2=0
sums=c1+c2+num
if(sums<10):
re.val=sums
num=0
else:
num=1
re.val=sums%10
if(cur1 or cur2):
re.next=ListNode()
re=re.next
if(num==1):
re.next=ListNode(1)
return head
addTwoNumbers
21:合并两个有序链表
链接：21. 合并两个有序链表 - 力扣（LeetCode）
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if(not list1): return list2
if(not list2): return list1
if(list1.val<list2.val):
re=ListNode(list1.val)
list1=list1.next
else:
re=ListNode(list2.val)
list2=list2.next
cur=re
while list1 or list2:
if(not list1):
cur.next=list2
break
if(not list2):
cur.next=list1
break
if(list1.val<list2.val):
val=list1.val
list1=list1.next
else:
val=list2.val
list2=list2.next
cur.next=ListNode(val)
cur=cur.next
return re
mergeTwoLists
23:合并k个升序链表
链接：23. 合并 K 个升序链表 - 力扣（LeetCode）
链表转list，list转链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
re=[]
for node in lists:
while node:
re.append(node.val)
node=node.next
re.sort()
if(len(re)==0): return None
head=ListNode(re[0])
cur=head
for i in range(1,len(re)):
cur.next=ListNode(re[i])
cur=cur.next
return head
mergeKLists
25:K个一组翻转链表
链接：25. K 个一组翻转链表 - 力扣（LeetCode）
cur记录翻转前一个位置，left翻转起点，right翻转终点
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if(not head): return head
dummpy=ListNode(next=head)
cur,left,right=dummpy,head,dummpy
i=0
while right:
if(i==k):
tmp=right.next
right.next=None
cur.next=self.reverseList(left)
left.next=tmp
right,cur=left,left
left=left.next
i=0
i+=1
right=right.next
return dummpy.next
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
pre,cur=None,head
while cur:
tmp=cur.next
cur.next=pre
pre,cur=cur,tmp
return pre
reverseKGroup
标签：head,ListNode,cur,val,self,next,链表,Leetcode,刷题 From： https://www.cnblogs.com/xiaoruru/p/18052083