链表


(1)链表的中间节点

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slow=fast=head
        while fast and fast.next:
            slow=slow.next
            fast=fast.next.next
        return slow

# 快慢指针

(2)合并两个有序链表

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1: return l2
        if not l2: return l1
        if l1.val<l2.val:
            l1.next=self.mergeTwoLists(l1.next,l2)
            return l1
        else:
            l2.next=self.mergeTwoLists(l1,l2.next)
            return l2

# 递归

(3)445.两数相加 II

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外,这两个数字都不会以零开头。

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        s1,s2=[],[]
        while l1:
            s1.append(l1.val)
            l1=l1.next
        while l2:
            s2.append(l2.val)
            l2=l2.next
        ans,carry=None,0

        while s1 or s2 or carry != 0:
            a = 0 if not s1 else s1.pop()
            b = 0 if not s2 else s2.pop()
            cur = a + b + carry
            cur,carry=cur%10,cur//10

            curnode = ListNode(cur)

            curnode.next = ans 
            ans = curnode           #头部接入
        return ans

# 栈,链表

(4)环形链表

给定一个链表,判断链表中是否有环。

class Solution(object):
    def hasCycle(self, head):
        if(not head or not head.next): return False
        slow,fast=head,head.next
        while(slow!=fast):
            if(not fast or not fast.next): return False
            slow=slow.next
            fast=fast.next.next
        return True

#快慢指针
# 1.slow放在head, fast放在head.next
# 2.while(slow!=fast)来移动指针

(5)环形链表II

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        fast,slow=head,head
        while True:
            if not fast or not fast.next: return 
            fast,slow=fast.next.next,slow.next
            if fast==slow: break
        fast=head
        while fast!=slow:
            fast,slow=fast.next,slow.next
        return fast

# 记f,s分别为快慢指针走过的节点。
# 记a,b分别为环外、环内节点数
# f=2s=s+nb,s=nb.
# 更换指向后:f'=a,s=nb+a,是重合的,在入口处。

(6)两两交换链表中的节点

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next: return head
        newhead=head.next
        head.next=self.swapPairs(newhead.next)
        newhead.next=head
        return newhead

文章作者: ╯晓~
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ╯晓~ !
评论
  目录