160.相交链表
【等比例法】
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
if not headA or not headB:
return None
pointA = headA
pointB = headB
while pointA != pointB:
pointA = pointA.next if pointA else headB #如果 pointA 是 None，那么 pointA 应该被重新设置为 headB。
pointB = pointB.next if pointB else headA
return pointA
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
lenA = self.getLength(headA)
lenB = self.getLength(headB)
# 通过移动较长的链表，使两链表长度相等
if lenA > lenB:
headA = self.moveForward(headA, lenA - lenB)
else:
headB = self.moveForward(headB, lenB - lenA)
# 将两个头向前移动，直到它们相交
while headA and headB:
if headA == headB:
return headA
headA = headA.next
headB = headB.next
return None
def getLength(self, head: ListNode) -> int:
length = 0
while head:
length += 1
head = head.next
return length
def moveForward(self, head: ListNode, steps: int) -> ListNode:
while steps > 0:
head = head.next
steps -= 1
return head
206.反转链表
【递归法】
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
return self.reverse(head, None)
def reverse(self, cur, pre):
if cur == None:
return pre
temp = cur.next
cur.next = pre
return self.reverse(temp, cur)
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
pre = None
while cur :
temp = cur.next
cur.next = pre
pre = cur
cur = temp
return pre
234.回文链表
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
cur = head
lists = []
while cur:
lists.append(cur.val)
cur = cur.next
return lists == lists[::-1]
141.环形链表
注意：是先让快慢指针跑起来，再看，快慢指针是否会相遇
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
fast = slow = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
return True
return False
142.环形链表||
没有交点，返回的是 None
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
visited = set()
while head:
if head in visited:
return head
else:
visited.add(head)
head = head.next
return None
21.合并两个有序链表
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if list1 is None: return list2
if list2 is None: return list1
if list1.val <= list2.val:
list1.next = self.mergeTwoLists(list1.next, list2)
return list1 #注意这里要有return
else:
list2.next = self.mergeTwoLists(list2.next, list1)
return list2 #注意这里要有return
2.两数相加
方法一：递归
方法二：迭代，初始化一个空链表，每次循环，往链表的末尾添加一个节点
class Solution:
# l1 和 l2 为当前遍历的节点，carry 为进位
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode], carry=0) -> Optional[ListNode]:
# 递归边界：l1 和 l2 都是空节点
if l1 is None and l2 is None:
return ListNode(carry) if carry else None # 如果进位了，就额外创建一个节点
# 如果 l1 是空的，那么此时 l2 一定不是空节点
if l1 is None:
l1, l2 = l2, l1 # 交换 l1 与 l2，保证 l1 非空，从而简化代码
carry += l1.val + (l2.val if l2 else 0) # 节点值和进位加在一起
l1.val = carry % 10 # 每个节点保存一个数位
l1.next = self.addTwoNumbers(l1.next, l2.next if l2 else None, carry // 10) # 进位
return l1
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
cur = dummy = ListNode() #哨兵节点，否则第一次循环，无法在一个空节点末尾添加节点
carry = 0 #进位
while l1 or l2 or carry:
carry += (l1.val if l1 else 0) + (l2.val if l2 else 0) #节点值和进位值 加在一起
cur.next = ListNode(carry%10) #每个节点保存一位进位
carry //= 10 #新的进位
cur = cur.next #下一个节点
if l1:
l1 = l1.next #下一个节点
if l2:
l2 = l2.next #下一个节点
return dummy.next
