Leetcode-15。链表双指针问题的Python解法,leetcode15,题目,python,解答

发表时间:2021-05-11

引言

双指针指的是在循环遍历时采用两个指针进行扫描(指针方向可以是相同方向也可以是相反方向)。链表题目常用的相同方向的双指针即快慢指针, fast 指针与 slow 指针从同一侧遍历,以不同的速度进行移动。

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

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
使用一趟扫描实现

示例:

输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]

思路:

我们可以设想假设设定了双指针p和q的话,当q指向末尾的NuLL,p与q之间相隔的元素个数为n时,那么删除掉p的下一个指针就完成了要求。

# 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: ListNode, n: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head 
        p = dummy
        q = dummy
        # 移动q直至p与q之间元素相隔n个
        for _ in range(n+1):
            q = q.next
        
        while q != None:
            p = p.next
            q = q.next
        # 循环结束时,q == None,p指针指向倒数第n+1个点,必须是倒数第n个节点的前一个节点
        p.next = p.next.next
        return dummy.next  # 针对只有一个节点或者删除头节点的特殊情况的

83. 删除排序链表中的重复元素

存在一个按 升序 排列的链表,给你这个链表的头节点 head ,请你删除所有重复的元素,使每个元素 只出现一次 。
返回同样按升序排列的结果链表。

示例:

输入:head = [1,1,2]
输出:[1,2]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        """利用排序链表的性质"""
        cur = head
        while cur and cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        
        return head

82. 删除排序链表中的重复元素 II

存在一个按升序排列的链表,给你这个链表的头节点 head ,请你删除链表中所有存在数字重复情况的节点,只保留原始链表中 没有重复出现 的数字。
返回同样按升序排列的结果链表。

示例:

输入:head = [1,2,3,3,4,4,5]
输出:[1,2,5]

pre 指针指向 dummy cur 指针指向 head
如果 pre.next 指向的值不等于 cur.next 指向的值,则两个指针都前进一位
否则,就单独移动cur,cur不断往前走,直到 pre.next 指向的值不等于 cur.next 指向的值。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        # 特殊情况处理
        if head == None or head.next == None:
            return head
        # dummy方便边界处理
        dummy = ListNode(0)
        dummy.next = head
        pre = dummy
        cur = head
        while cur != None and cur.next != None:
            if pre.next.val != cur.next.val:
                pre = pre.next
                cur = cur.next
            else:
                while cur and cur.next and pre.next.val == cur.next.val:
                    cur = cur.next
                # 循环结束条件是pre.next.val != cur.next.val或者是cur == None
                pre.next = cur.next
                cur = cur.next
        return dummy.next

141. 环形链表

给定一个链表, 判断链表中是否有环
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示 链表尾连接到链表中的位置 (索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
如果链表中存在环,则返回 true 。 否则,返回 false 。

示例:

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

思路:

这道题是快慢指针的经典应用。
设置两个指针,一个每次走一步的慢指针和一个每次走两步的快指针。
如果不含有环,跑得快的那个指针最终会遇到null,说明链表不含环
如果含有环,快指针会超慢指针一圈,和慢指针相遇,说明链表含有环。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        # 利用快慢指针,慢指针每次走一步,快指针每次走两步,如果链表中有环,则它们会相遇
        dummy = ListNode(0)
        dummy.next = head

        slow = dummy
        fast = dummy

        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
            if fast == slow:
                return True
        return False

142. 环形链表 II

给定一个链表,返回 链表开始入环的第一个节点 。 如果链表无环,则返回 null。
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意,pos 仅仅是用于标识环的情况,并不会作为参数传递到函数中。

思路:

双指针第一次相遇:
设两指针fast,slow指向链表头部head,fast 每轮走2步,slow每轮走1步;
第一种结果: fast 指针走过链表末端,说明链表无环,直接返回null;
TIPS:若有环,两指针一定会相遇。因为每走1轮,fast 与slow的间距+1,fast终会追上slow;
第二种结果:当fast == slow时,两指针在环中第一次相遇。下面分析此时fast 与slow走过的步数关系:
设链表共有a+b个节点,其中链表头部到链表入口有a个节点(不计链表入口节点),链表环有b个节点;设两指针分别走了f,s步,则有:
fast走的步数是slow步数的2倍,即f = 2s;fast 比 slow多走了n个环的长度,即f=s +nb;
以上两式相减得:f= 2nb,s = nb,即fast和slow指针分别走了2n, n个环的周长

双指针第二次相遇:
slow指针位置不变,将fast指针重新指向链表头部节点;slow和fast同时每轮向前走1步;
TIPS:此时f =0, s = nb ;
当fast指针走到f=a步时,slow指针走到步s = a+nb,此时 两指针重合,并同时指向链表环入口

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head

        # 设置快慢指针
        slow = dummy
        fast = dummy
        # 构造第一次相遇
        while True:
            # 链表无环
            if fast.next == None or fast.next.next == None:
                return None
            slow = slow.next
            fast = fast.next.next
            # 双指针第一次相遇
            if slow == fast:
                break
        
        # 构造第二次相遇
        fast = dummy
        while True:
            fast = fast.next
            slow = slow.next
            if fast == slow:
                break
        return slow

程序员代码面试指南-两个单链表相交的一系列问题

这道题号称链表中最难问题,本质是几个简单问题的嵌套问题

  • 在本题中,单链表可能有环,也可能无环。给定两个单链表的头节点head1和head2,这两个链表可能相交,也可能不相交。请实现一个函数,如果两个链表相交,请返回相交的第一个节点;如果不相交,返回null即可.
  • 如果链表1的长度为N,链表2的长度为M,时间复杂度请达到O(N+M),额外空间复杂度请达到O(1)

思路:

  • 首先判断链表是否有环(问题1)
  • 若两个链表都没有环,转而判断两个无环链表是否相交
  • 若两个链表都有环,转而判断两个有环链表是否相交
  • 若一个链表有环,一个链表无环,则肯定不会相交

问题1:判断链表是否有环?

设置一个慢指针和一个快指针。从链表头结点开始,慢指针一次走一步,慢指针一次走两步·
如果链表无环,则快指针会移动到终点null
如果链表有环,则快指针和慢指针会相遇。相遇后令快指针回到头节点,接着快慢指针都一次走一步,两者再次相遇的节点就是入环节点

问题2:若两个链表都没有环,转而判断 两个无环链表是否相交

  • 先分别遍历两个链表,得到两个链表的的长度:len1和len2
  • 如果链表1更长,则链表1先走len1 - len2步;否则,链表2先走len2 -len1步
  • 然后两个链表一起走,一次走一步,相遇的节点就是 相交节点

问题3:若两个链表都有环,转而判断两个有环链表是否相交

  • 先得到两个有环链表的入环节点loopNode1和loopNode2
  • 如果 loopNode1 == loopNode2 ,那么两个链表必然相交((有公共的环)而且相交节点必然位于入环节点之前(包含入环节点)。入环之前的链表部分没有环,所以求相交节点的方法同问题二,只是将链表终点从null换成了loopNode1
    在这里插入图片描述
  • 如果 loopNode1 != loopNode2 ,那么两个链表可能相交也可能不相交,相交的情况也只可能发生在环节点中。从loopNode1开始绕圈遍历节点,再绕回到loopNode1 之前如果遇到loopNode2 ,说明相交,返回loopNode1或loopNode2都行,都算相交节点。如果绕回loopNode1的过程中一直没碰上loopNode2,说明不相交
    在这里插入图片描述
# 问题一
def getLoopNode(head):
    if head == None or head.next == None or head.next.next == None:
        return None
    slow = head.next
    fast = head.next.next
    while slow != fast:
        if fast.next == None or fast.next.next == None:
            return None
        slow = slow.next
        fast = fast.next.next
    fast = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    return slow
# 问题二
def noLoop(head1, head2):
    if head1 == None or head2 == None:
        return None
    cur1 = head1
    cur2 = head2
    n = 0
    while cur1.next != None:
        n += 1
        cur1 = cur1.next
    while cur2.next != None :
        n -= 1
        cur2 = cur2.next
    if cur1 != cur2:
        return None 
    cur1 = head1 if n >= 0 else head2
    cur2 = head1 if cur1 == head2 else head2
    # n = len1-len2
    n = abs(n)
    while n != 0:
        cur1 = cur1.next 
        n -= 1
    while cur1 != cur2:
        cur1 = cur1.next
        cur2 = cur2.next
    return cur1
# 问题三:
def bothLoop(head1, node1, head2, node2):
    if head1 == None or head2 == None:
        return None
    # 入环之前就相交
    if node1 == node2:
        cur1 = head1
        cur2 = head2
        n = 0
        while cur1 != node1:
            n += 1
            cur1 = cur1.next
        while cur2 != node1:
            n -= 1
            cur2 = cur2.next
        cur1 = head1 if n >= 0 else head2
        cur2 = head1 if cur1 == head2 else head2
        n = abs(n)
        while n != 0:
            n -= 1
            cur1 = cur1.next
        while cur1 != cur2:
            cur1 = cur1.next
            cur2 = cur2.next
        return cur1
    # 入环之后才相交
    else:
        cur1 = node1.next
        while cur1 != node1:
            if cur1 == node2:
                return node1
            cur1 = cur1.next
        return None
#主函数
class Node:
    def __init__(self, val=None):
        self.val = val
        self.next = None

def getIntersectNode(head1, head2):
    if head1 == None or head2 == None:
        return None
    # 获得两个链表的入环指针,如果是无环链表,返回None
    node1 = getLoopNode(head1)
    node2 = getLoopNode(head2)
    # 如果是无环链表
    if node1 == None and node2 == None:
        return noLoop(head1, head2)
    # 如果是有环链表
    if node1 != None and node2 != None:
        return bothNode(head1, node1, head2, node2)
    return None

234. 回文链表

请判断一个链表是否为回文链表。

示例:

输入: 1->2
输出: false

思路:

这道题目可以用快慢指针+反转链表解决。

  1. 使用快慢指针找到链表的中间位置,然后将链表分为两个部分
  2. 反转后半部分链表
  3. 逐一对比前后两部分链表
  4. 恢复链表
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        # 特殊情况
        if head == None:
            return False
        # 寻找列表中间位置
        mid = self.findMid(head)
        # 将后半段链表翻转过来
        reverse_start = self.reverse(mid.next)
        # 判断回文
        first = head
        second = reverse_start
        # 后面的个数小于等于前面
        while second != None:
            if first.val != second.val:
                return False
            first = first.next
            second = second.next
        return True

        # 还原链表并返回结果,最好不对链表做改变
        mid.next = self.reverse(reverse_start)
        
    def reverse(self,head):
        pre = None
        cur = head
        while cur != None:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        # 循环结束时,pre指向链表头部
        return pre

    def findMid(self,head):
        slow = head
        fast = head
        while fast.next and fast.next.next:
            # 慢指针一次移动一个位置,快指针一次移动两个位置
            slow = slow.next
            fast = fast.next.next
        return slow

328. 奇偶链表

给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是 节点编号的奇偶性 ,而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1),时间复杂度应为 O(nodes),nodes 为节点总数。
说明:
应当保持奇数节点和偶数节点的相对顺序。
链表的第一个节点视为奇数节点,第二个节点视为偶数节点,以此类推。

示例:

输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        # 将链表分离成奇数链表与偶数链表,然后在拼接到一起
        if head == None:
            return head
        # 构造奇数链表与偶数链表的虚拟头结点
        dummy1 = even = ListNode(0) 
        dummy2 = old = ListNode(0)

        cur = head
        while cur != None:
            old.next = cur
            old = old.next
            cur = cur.next
            if cur:
                even.next = cur
                even = even.next
                cur = cur.next
        # 循环结束时,cur==None;old与even都指向奇数链表与偶数链表的尾结点
        old.next = dummy1.next
        even.next =None
        return dummy2.next

如果对您有帮助,麻烦点赞关注,这真的对我很重要!!!如果需要互关,请评论或者私信!
在这里插入图片描述


文章来源互联网,如有侵权,请联系管理员删除。邮箱:417803890@qq.com / QQ:417803890

微配音

Python Free

邮箱:417803890@qq.com
QQ:417803890

皖ICP备19001818号-4
© 2019 copyright www.pythonf.cn - All rights reserved

微信扫一扫关注公众号:

联系方式

Python Free