(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)

简介: (剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)

18、删除链表的节点

问题描述:

难度:简单

给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。返回删除后的链表的头节点。

注意:此题对比原题有改动

示例 1:

输入: head = [4,5,1,9], val = 5

输出: [4,1,9]

解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.

示例 2:

输入: head = [4,5,1,9], val = 1

输出: [4,5,9]

解释: 给定你链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9.

代码部分
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        newHead = ListNode(0,head)
        newHead.next = head
        pre, curr = newHead,head
        while curr:
            if curr.val == val:
                pre.next = curr.next
            else:
                pre =curr
            curr = curr.next
        return newHead.next

22、链表中倒数第K个节点

问题描述

难度:简单

输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。

例如,一个链表有 6 个节点,从头节点开始,它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例:

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

代码部分
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        slow = head
        fast = head
        for _ in range(k):
            if fast == None:
                return fast
            fast = fast.next
        while fast:
            slow = slow.next
            fast = fast.next
        return slow

25、合并两个排序的链表

问题描述

难度:简单

输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1:

输入:1->2->4, 1->3->4

输出:1->1->2->3->4->4

解题思路

利用归并排序的思想。

创建一个新的链表节点作为头节点(记得保存),然后判断 l1和 l2 头节点的值,将较小值的节点添加到新的链表中。

当一个节点添加到新的链表中之后,将对应的 l1 或 l2 链表向后移动一位。

然后继续判断当前 l1 节点和当前 l2 节点的值,继续将较小值的节点添加到新的链表中,然后将对应的链表向后移动一位。

这样,当 l1 或 l2 遍历到最后,最多有一个链表还有节点未遍历,则直接将该节点链接到新的链表尾部即可。

解题代码
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        newHead = ListNode(-1)
        curr = newHead
        while l1 and l2:
            if l1.val <l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next
        curr.next = l1 if l1 is not None else l2#当两个链表不相等的时候
        return newHead.next

52、两个链表的第一个公共节点

问题描述

难度:简单

输入两个链表,找出它们的第一个公共节点。

如下面的两个链表:

在节点 c1 开始相交。

示例 1:

输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3

输出:Reference of the node with value = 8

输入解释:相交节点的值为 8 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。

示例 2:

输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1

输出:Reference of the node with value = 2

输入解释:相交节点的值为 2 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。

示例 3:

输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2

输出:null

输入解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。

解释:这两个链表不相交,因此返回 null

解题思路

如果两个链表相交,那么从相交位置开始,到结束,必有一段等长且相同的节点。假设链表 A 的长度为 m、链表 B 的长度为 n,他们的相交序列有 k 个,则相交情况可以如下如所示:

现在问题是如何找到 m-k 或者 n-k 的位置。

考虑将链表 A 的末尾拼接上链表 B,链表 B 的末尾拼接上链表 A。

然后使用两个指针 pA 、PB,分别从链表 A、链表 B 的头节点开始遍历,如果走到共同的节点,则返回该节点。

否则走到两个链表末尾,返回 None。

解题代码
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return None
        pA = headA
        pB = headB
        while pA != pB:
            pA = pA.next if pA else headB
            pB = pB.next if pB else headA
        return pA
相关文章
|
2月前
|
算法
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
69 1
|
2月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
22 0
LeetCode第二十四题(两两交换链表中的节点)
|
2月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
44 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
2月前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
32 0
|
7月前
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解
|
6月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
6月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
6月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
60 2
|
7月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
53 1
|
6月前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表