链表

此贴为笔者学习左神算法的记录。【题目】 给定一个链表的头节点 head，请判断该链表是否为回文结构。 例如： 1->2->1，返回 true。 1->2->2->1，返回 true。 15->6->15，返回 true。 1->2->3，返回 false。 进阶： 如果链表长度为 N，时间复杂度达到 O(N)，额外空间复杂度达到 O(1)。【解答】 方法一： 方法一是最容易实现的方法，利用栈结构即可。从左到右遍历链表，遍历的过程中把每个节点依次压入栈中。因为栈是先进后出的，所以在遍历完成后，从栈顶到栈底的节点值出现顺序会与原链表从左到右的值...

链表（Linked list）是一种物理存储单元上非连续的数据结构、数据元素的逻辑顺序是通过链表中的指针实现的。由于不必按顺序存储，链表在插入的时候可以达到 O(1) 的复杂度，但链表查找的时候由于不能通过索引查找，所以查找的时间复杂度是 O(n) 。常见的链表有单向链表，双向链表，以及环形链表。  单向链表 单向链表是最简单的一种链表，一般只包含存储的数据和指针（这里的指针不是 C 语言中的地址指针，他是下一个节点的引用），每个指针指向下一个节点，最后一个节点指向空，如下图所示。为了方便在尾部添加节点，我们新增一个 tail 变量，指向链表的尾节点。  单向链表的节点类如下： private...

【题目】 据说著名犹太历史学家 Josephus 有过以下故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus 及他的朋友躲到一个洞中，39 个犹太人决定宁愿死也不要被敌人抓到，于是决定了一种自杀方式，41 个人排成一个圆圈，由第 1 个人开始报数，报数到 3 的人就自杀，然后再由下一个人重新报 1，报数到 3 的人再自杀，这样依次下去，直到剩下最后一个人时，那个人可以自由选择自己的命运。这就是著名的约瑟夫问题。现在请用单向环形链表描述该结构并呈现整个自杀过程。 输入：一个环形单向链表的头节点 head 和报数的值 m。 返回：最后生存下来的节点，且这个节点自己组成环形单向链表，其他...

此贴为笔者学习左神算法的记录。【题目】 给定一个单向链表的头节点 head，节点的值类型是整型，再给定一个整数 pivot。实现一个调整链表的函数，将链表调整为左部分都是值小于 pivot 的节点，中间部分都是值等于 pivot 的节点，右部分都是值大于 pivot 的节点。除这个要求外，对调整后的节点顺序没有更多的要求。 例如：链表 9->0->4->5->1，pivot=3。 调整后链表可以是 1->0->4->9->5，也可以是 0->1->9->5->4。总之，满足左部分都是小于 3的节点，中间部分都是等于 3 的...

【题目】 一种特殊的链表节点类描述如下：  public class Node { private int value; private Node next; private Node rand; public Node(int data) { this.value = data; } }  Node 类中的 value 是节点值，next 指针和正常单链表中 next 指针的意义一样，都指向下一个节点，rand 指针是 Node 类中新增的指针，这个指针可能指向链表中的任意一个节点，也可能指向 null。 给定一个由 Node 节点类型组成的无环单链表的头节点 head，请实现一个函数完成这...

【题目】 分别实现反转单向链表和反转双向链表的函数。 【要求】 如果链表长度为 N，时间复杂度要求为 O(N)，额外空间复杂度要求为 O(1)。public class ReverseList { class Node { private int value; private Node next; public Node(int value) { this.value = value; } } class DoubleNode { private int value; private DoubleNode next; private DoubleNode last; public Double...

【题目】 分别实现两个函数，一个可以删除单链表中倒数第 K 个节点，另一个可以删除双链表中倒数第 K 个节点。 【要求】 如果链表长度为 N，时间复杂度达到 O(N)，额外空间复杂度达到 O(1)。【解答】 本题较为简单，实现方式也是多种多样的，这里供一种方法供读者参考。 先来看看单链表如何调整。如果链表为空或者 K 值小于 1，这种情况下，参数是无效的，直接返回即可。除此之外，让链表从头开始走到尾，每移动一步，就让 K 的值减 1。 链表：1->2->3，K = 4，链表根本不存在倒数第 4 个节点。 走到的节点：1 -> 2 -> 3 K 变化为：3 2 1 链表：...

【题目】 给定两个有序链表的头指针 head1 和 head2，打印两个链表的公共部分。【解答】 本题难度很低，因为是有序链表，所以从两个链表的头开始进行如下判断： 1. 如果 head1 的值小于 head2，则 head1 往下移动。 2. 如果 head2 的值小于 head1，则 head2 往下移动。 3. 如果 head1 的值与 head2 的值相等，则打印这个值，然后 head1 与 head2 都往下移动。 4. head1 或 head2 有任何一个移动到 null，则整个过程停止。 具体过程参看如下代码中的 printCommonPart 方法。 public class...

在JavaScript的世界里，算法不仅是解决问题的艺术，更是提升程序性能和可维护性的基石。今天，我们将深入探讨一个基础而重要的算法问题——合并两个有序链表。此问题不仅常见于面试题，也频繁出现在需要高效数据整合的实际项目中。通过本文，你将学会如何巧妙地合并两个已排序的链表，并理解其背后的逻辑与实现细节。 二、技术概览 2.1 起源与发展 合并两个有序链表的算法源于基础的数据结构与算法领域，它涉及到链表这一线性数据结构的操作。随着算法理论的发展，该问题的解决方案不断被优化，从传统的迭代、递归方法到现代语言特性的运用，展示了算法技术的演进历程。 2.2 核心特点  高效合并：利用链表的特性，可以在...

【题目】 给定链表的头节点 head，实现删除链表的中间节点的函数。 例如： 不删除任何节点； 1->2，删除节点 1； 1->2->3，删除节点 2； 1->2->3->4，删除节点 2； 1->2->3->4->5，删除节点 3； 进阶： 给定链表的头节点 head、整数 a 和 b，实现删除位于 a/b 处节点的函数。 例如： 链表：1->2->3->4->5，假设 a/b 的值为 r。 如果 r 等于 0，不删除任何节点； 如果 r 在区间(0, 1/5]上，删除节点 1； 如果 r 在区间(1/5, ...

一、引言 在JavaScript编程的广阔天地中，算法技术是构筑高效应用的基石。掌握巧妙的算法不仅能优化代码性能，还能在面试中脱颖而出。本文聚焦于“删除链表的倒数第N个结点”这一经典问题，它不仅考验开发者对链表数据结构的理解，还涉及巧妙的指针操作技巧。通过本文，你将掌握一种高效且优雅的解决方案，并理解其背后的设计哲学。 二、技术概览 2.1 起源与发展 链表操作是数据结构与算法课程的基石，而删除链表特定位置的结点是基本操作之一。随着算法理论的发展，特别是对于链表遍历和指针技巧的深入研究，形成了多种高效解决此类问题的方法。 2.2 核心特点  指针追踪：利用双指针策略，一快一慢，精确定位倒数第N...

Leetcode、牛客、PTA原题：“回文链表”和“合并有序链表”一、题目要求：回文链表解题：代码： class Solution { public boolean isPalindrome(ListNode head) { ListNode p1 = replace(head); while(head != null && p1 != null){ // 存在不同值的节点时 if(head.val != p1.val){ return false; } head = head.next; p1 = p1.next; } return true; } // 反转链表 publi...

【题目】 假设链表中每一个节点的值都在 0～9 之间，那么链表整体就可以代表一个整数。例如：9->3->7，可以代表整数 937。给定两个这种链表的头节点 head1 和 head2，请生成代表两个整数相加值的结果链表。例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。【解答】 这道题难度较低，考查面试者基本的代码实现能力。一种实现方式是将两个链表先算出各 自所代表的整数，然后求出两个整数的和，最后将这个和转换成链表的形式，但是这种方法有 一个很大的问题，链表的长度可以很长，可以表达一个很大...

/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pHead ListNode类 * @param k int整型 * @return ListNode类 */ ListNode* FindKthToTail(ListNode* pHead, int k) { ...

import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ public ListNode deleteDuplicates (ListNo...

import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pHead ListNode类 * @param k int整型 * @return ListNode类 */ public ListNode FindKt...

import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param head ListNode类 the head node * @return ListNode类 */ public ListNode sortInList...

import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ public ListNode deleteNodes (ListNode he...

import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ public ListNode ReverseList (ListNode he...