目录

AaronJny

诗酒繁华,书剑天涯。

标签: 链表 (3)

leetcode题解第24题 Swap Nodes in Pairs (两两交换链表中的节点)

题外话:之前说了写了代码也不一定会写题解,因为懒,然后我就真的没写……题目断断续续坚持在做,这代码都是好早之前写的了,题解嘛……果然,我就是个鸽子,咕咕咕。 反正你们应该也不需要我的题解,毕竟网上那么多,我就写着做个纪念。 好了,说正题。题目的大意是: 给定一个链表,你需要两两交换其中相邻的节点,并返回交换后的链表。但是你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。 样例输入: 1->2->3->4 样例输出: 2->1->4->3 从示例可以看出,第一个节点和第二个节点做了交换,第三个节点和第四个节点做了交换。 leetcode 中的 python 链表是这样定义的: class ListNode: def __init__(self, x): self.val = x self.next = None 这就是一个简单的模拟题,直接上代码吧,注释很详细: class Solution: def swapPairs(self, head: ListNode) -> ListNode: """ 两两交换给定链表的节....

leetcode题解第23题 Merge k Sorted Lists(合并K个排序链表)

题目大意如下: 给定 k 个有序链表,请将这 k 个列表合并成一个有序链表,然后返回这个有序列表的头结点。 在 python 中,链表被这样实现: # Definition for singly-linked list. class ListNode: def __init__(self, x): self.val = x self.next = None 样例输入: [ 1->4->5, 1->3->4, 2->6 ] 样例输出: 1->1->2->3->4->4->5->6 题目链接:https://leetcode.com/problems/merge-k-sorted-lists 解题思路: 这道题考察的是链表的操作和归并排序,只不过这里做的是多个列表的归并。 输入是一个链表头结点组成的列表,我们需要创建一个指向这些链表头结点的指针构成的列表,和一个结果链表。 比较所有指针对应的值的大小,获取最小的节点的值,创建新节点,加入到结果链表中。然后将指向最小节点的指针后移一位。当一个指针走到头时,这....

leetcode题解第19题 Remove Nth Node From End of List(删除链表的倒数第N个节点)

考查列表操作的一道题,题目大意如下: 给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。 样例输入: head = 1->2->3->4->5 n = 2 样例输出: 1->2->3->5 题目链接:https://leetcode.com/problems/remove-nth-node-from-end-of-list/ emmmm,题目相当简单,所以本来没打算写的,不过交了一发,时间击败了 100% python 代码,有点特别意义,就简单说一下吧。 解题思路: 我的想法很简单,先利用指针遍历一下链表,计算链表的长度 length。 然后从头开始,将指针移动到 length-n-1 的位置,改变一下节点的 Next 的值就行了。 样例代码: class Solution(object): def list_len(self, head): """ 计算给定链表的长度 :param head: :return: """ tmp_head = head cnt = 0 while tmp_head: cn....