二刷力扣--链表

简介: 二刷力扣--链表

链表

链表类型:

单链表(可以访问后面的一个节点)

双链表(可以访问前后节点)

循环链表(最后一个节点指向首节点)

在Python中定义单链表节点:

class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

移除链表元素 203.

#链表删除 #哑节点

给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点

为了统一处理删除操作,在head节点前添加一个哑节点

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        pre = dummy
        cur = dummy.next
        while cur:
            if cur.val == val:
                pre.next = cur.next 
                cur = cur.next
            else:
                pre = pre.next
                cur = cur.next
        
        return dummy.next

Python有垃圾回收,不需要手动删除节点。

设计链表 707.

你可以选择使用单链表或者双链表,设计并实现自己的链表。

单链表中的节点应该具备两个属性:valnextval 是当前节点的值,next 是指向下一个节点的指针/引用。

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class MyLinkedList:
    def __init__(self):
        self.dummy = Node(-1, None)
        self.max_index = -1  

    def get(self, index: int) -> int:
        if index < 0 or index > self.max_index:
            return -1
        cur = self.dummy.next 
        for  i in range(index):
            cur = cur.next
        return cur.val

    def addAtHead(self, val: int) -> None:
        self.dummy.next  = Node(val, self.dummy.next)
        self.max_index += 1

    def addAtTail(self, val: int) -> None:
        cur = self.dummy
        while cur.next:
            cur = cur.next
        cur.next = Node(val)
        self.max_index += 1

    def addAtIndex(self, index: int, val: int) -> None:
        if  index < 0 or index > self.max_index + 1:
            return 
        cur = self.dummy
        i = 0
        for i in range(index):
            cur = cur.next

        cur.next = Node(val, cur.next)
        self.max_index += 1

    def deleteAtIndex(self, index: int) -> None:
        if  index < 0 or index > self.max_index:
            return 
        cur = self.dummy
        for i in range(index):
            cur = cur.next

        cur.next = cur.next.next 
        self.max_index -= 1

反转链表 206.

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

#双指针

使用temp保存cur.next ,因为反转后cur.next就改变了,无法再访问原来的下一个元素了。

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
      pre = None
      cur = head
      while cur:
        temp = cur.next # 下一个节点
        cur.next  = pre # 反转next方向

        pre = cur
        cur = temp # 去下一个
      
      return pre 

两两交换链表中的节点 24.

#哑节点

给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

有些题解里很多cur.next.next.next,看起来很麻烦。 用临时节点记录一下似乎就不用那么多next了。而且也不用考虑.next赋值的顺序了。

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        cur = dummy
        # 交换cur后面的两个节点
        while cur.next and cur.next.next:
            node1 = cur.next        
            node2 = node1.next  
            node3 = node2.next  
            #  cur->node1->node2-->node3(node2.next)  ----> cur->node2->node1-->node3(node2.next)  
            cur.next = node2  
            node2.next = node1 
            node1.next = node3
           
            cur = node1 
        
        return dummy.next

删除链表的倒数第N个节点 19.

#双指针 #哑节点

双指针的应用。快指针fast先走n步,当快指针到达倒数第1个节点时,慢指针slow到达倒数n+1个节点,删除slow的下一个节点。

哑节点对简化删除操作很有用,如果不用哑节点,删除head就要特殊处理。

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        fast = dummy
        slow = dummy
        # 当fast 到达倒数第1个节点, slow到达倒数第n+1个节点
        for i in range(n):
            fast = fast.next
        while fast.next :
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next 
        return dummy.next 

链表相交 面试题 02.07. 同 160

#双指针

给你两个单链表的头节点 headAheadB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null

两个链表如果有相同的节点,则从相同节点开始,一直到末尾都是相同的。

让较长的链表先走 abs(lengthA-lengthB)个节点,然后比较两个链表。

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        def getLength(head):
            length = 0
            while head:
                head = head.next
                length += 1
            return length
        lengthA = getLength(headA)
        lengthB = getLength(headB) 
        Long, Short = (headA, headB) if lengthA > lengthB  else (headB, headA)

        for _ in range (abs(lengthA- lengthB)):
            Long = Long.next
        while Short:
            if Short == Long:
                return Short
            else:
                Short = Short.next
                Long = Long.next
        return None
      


环形链表II 142.

#集合 #双指针

  1. 直接用set记录访问过的节点,再次遇到则表明出现了环。
cla

双指针。快指针fast一次走两步,慢指针slow一次走一步。如果有环,两个指针一定会遇到。

而找到环的入口比较难,需要推导一下。(这个不太好理解,推荐看代码随想录的视频)

相遇时,slow指针走过的节点数是 x+y, fast走过的节点数是 x+y+ n(y+z) ,n>=1

fast一次走两个节点,所以走过的节点数是slow的两倍,即 x+y+n(y+z) = 2(x+y)。 化简一下,得到 x = (n-1)(y+z) + z

n = 1时, x = z 也就是说,一个指针index1从slow与fast相遇点出发,一个指针index2从头节点出发,会在入口节点相遇。

n大于1时和n为1的时候 效果是一样的,一样可以通过这个方法找到 环形的入口节点,只不过,index1 指针在环里 多转了(n-1)圈,然后再遇到index2,相遇点依然是环形的入口节点

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast = head
        slow = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if slow == fast:
                index1 = fast
                index2 = head
                while index1 != index2:
                    index1 = index1.next
                    index2 = index2.next
                return index2
        
        return None

链表小结

哑节点对简化链表操作很有用。添加一个哑节点,对头节点的处理会和其他节点一样。

双指针是常用的方法,可以用来判断链表是否有环,找到链表倒数第n个元素。

相关文章
|
21天前
|
Java
力扣经典150题第五十八题:合并两个有序链表
力扣经典150题第五十八题:合并两个有序链表
16 2
|
21天前
|
Java
力扣经典150题第六十题:反转链表 II
力扣经典150题第六十题:反转链表 II
11 1
|
21天前
|
存储 Java
力扣经典150题第五十九题: 随机链表的复制
力扣经典150题第五十九题: 随机链表的复制
13 1
|
1月前
|
算法 Java
[Java·算法·中等] LeetCode21. 合并两个有序链表
[Java·算法·中等] LeetCode21. 合并两个有序链表
19 2
|
1月前
|
存储 算法 Python
二刷力扣--哈希表
二刷力扣--哈希表
|
1月前
|
算法
二刷力扣--二叉树(3)
二刷力扣--二叉树(3)
|
1月前
二刷力扣--二叉树(2)
二刷力扣--二叉树(2)
|
1月前
二刷力扣--二叉树(1)基础、遍历
二刷力扣--二叉树(1)基础、遍历
|
1月前
|
存储 算法 Python
二刷力扣--栈和队列
二刷力扣--栈和队列
|
1月前
|
算法 索引 Python
二刷力扣--字符串
二刷力扣--字符串