一 简介

• 单链表中的每个结点不仅包含值，还包含链接到下一个结点的引用字段。
  

1.1 结点结构

// Definition for singly-linked list.public class SinglyListNode { int val; SinglyListNode next; SinglyListNode(int x) { val = x; }}

1.2 操作

• 与数组不同，我们无法在常量时间内访问单链表中的随机元素。
• 如果我们想要获得第 i 个元素，我们必须从头结点逐个遍历。 我们按索引来访问元素平均要花费 O(N) 时间，其中 N 是链表的长度。

1.3 添加操作 - 单链表

如果我们想在给定的结点 prev 之后添加新值，我们应该：

• 1. 使用给定值初始化新结点 cur；
• 2. 将 cur 的“next”字段链接到 prev 的下一个结点 next；
• 3. 将 prev 中的“next”字段链接到 cur 。

与数组不同，我们不需要将所有元素移动到插入元素之后,因此，您可以在 O(1) 时间复杂度中将新结点插入到链表中，这非常高效。

1.4 删除操作 - 单链表

如果我们想从单链表中删除现有结点 cur，可以分两步完成：

• 1. 找到 cur 的上一个结点 prev 及其下一个结点 next；
• 2. 接下来链接 prev 到 cur 的下一个节点 next。
• 第一步中，我们需要找出 prev 和 next。使用 cur 的参考字段很容易找出 next，但是，我们必须从头结点遍历链表，以找出 prev，它的平均时间是 O(N)，其中 N 是链表的长度。因此，删除结点的时间复杂度将是 O(N)。
• 空间复杂度为 O(1)，因为我们只需要常量空间来存储指针。

1.5 设计链表

设计链表的实现。您可以选择使用单链表或双链表。

• 单链表中的节点应该具有两个属性：val 和 next。
  • val 是当前节点的值
  • next 是指向下一个节点的指针/引用

如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：

• get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
• addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
• addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
• addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。
• deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

二 双指针技巧

2.1 给定一个链表，判断链表中是否有环。

可能已经使用哈希表提出了解决方案

• 想象一下，有两个速度不同的跑步者。如果他们在直路上行驶，快跑者将首先到达目的地。但是，如果它们在圆形跑道上跑步，那么快跑者如果继续跑步就会追上慢跑者。
• 这正是我们在链表中使用两个速度不同的指针时会遇到的情况：
  • 1. 如果没有环，快指针将停在链表的末尾。
  • 2. 如果有环，快指针最终将与慢指针相遇。

所以剩下的问题是：这两个指针的适当速度应该是多少？

• 一个安全的选择是每次移动慢指针一步，而移动快指针两步。每一次迭代，快速指针将额外移动一步。如果环的长度为 M，经过 M 次迭代后，快指针肯定会多绕环一周，并赶上慢指针。
  亲参考2.2图

public class Solution { public boolean hasCycle(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow.equals(fast)) { return true; } } return false; }}

2.2 返回链表开始入环的第一个节点

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

解题，有了2.1的基础，来计算一下。

public class Solution { public ListNode detectCycle(ListNode head) { if (head == null || head.next == null) { return null; } ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow.equals(fast)) { break; } } while (head != null && slow != null) { if (head.equals(slow)) { return slow; } head = head.next; slow = slow.next; } return null; }}

2.3 相交链表

(判断是否相交，可以遍历两个链表，看最后一个节点是否相等)
编写一个程序，找到两个单链表相交的起始节点。
例如，下面的两个链表：

A: a1 → a2 ↘ c1 → c2 → c3 ↗B: b1 → b2 → b3

在节点 c1 开始相交。
注意：

• 如果两个链表没有交点，返回 null.
• 在返回结果后，两个链表仍须保持原有的结构。
• 可假定整个链表结构中没有循环。
• 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

 /** * 返回相交单向链表的交点 */ public static ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) { return null; } //记录链表的长度 int lenA = 1; ListNode tempA = headA; while (tempA.next != null) { lenA++; tempA = tempA.next; } int lenB = 1; ListNode tempB = headB; while (tempB.next != null) { lenB++; tempB = tempB.next; } //判断链表是否相交，不想交直接返回null if (!tempA.equals(tempB)) { return null; } //截取后半段，相同长度的链表 int reduseCount = lenA - lenB; tempA = headA; tempB = headB; if (reduseCount > 0) { for (int i = 0; i < reduseCount; i++) { tempA = tempA.next; } } else { reduseCount = Math.abs(reduseCount); for (int i = 0; i < reduseCount; i++) { tempB = tempB.next; } } //循环遍历找到交点 while (tempB != null && tempA != null) { if (tempB.equals(tempA)) { return tempB; } tempA = tempA.next; tempB = tempB.next; } return null; }

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

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.当删除了倒数第二个节点后，链表变为 1->2->3->5.

• 说明：
  给定的 n 保证是有效的。
• 进阶：
  你能尝试使用一趟扫描实现吗？
• 解题思路
  • 典型的利用双指针法解题。首先让指针first指向头节点，然后让其向后移动n步，接着让指针sec指向头结点，并和first一起向后移动。当first的next指针为NULL时，sec即指向了要删除节点的前一个节点，接着让first指向的next指针指向要删除节点的下一个节点即可。
  • 注意如果要删除的节点是首节点，那么first向后移动结束时会为NULL，这样加一个判断其是否为NULL的条件，若为NULL则返回头结点的next指针。

 /** * 删除链表的倒数第 n 个节点 */ public static ListNode removeNthFromEnd(ListNode head, int n) { if (head == null) { return null; } if (n == 0) { return null; } ListNode first = head; ListNode sec = head; for (int i = 0; i < n; i++) { first = first.next; } while (first != null && first.next != null) { first = first.next; sec = sec.next; } if (sec.next == null) { return null; } sec.next = sec.next.next; return head; }

2.5小结

2.5.1 提示

• 1. 在调用 next 字段之前，始终检查节点是否为空。
  • 获取空节点的下一个节点将导致空指针错误。例如，在我们运行 fast = fast.next.next 之前，需要检查 fast 和 fast.next 不为空。
• 2. 仔细定义循环的结束条件。

2.5.2 复杂度分析

• 空间复杂度分析容易。如果只使用指针，而不使用任何其他额外的空间，那么空间复杂度将是 O(1)。

三 经典问题

3.1 反转链表

• 一种解决方案是按原始顺序迭代结点，并将它们逐个移动到列表的头部。
  

3.2 删除链表中的节点

删除链表中等于给定值 val 的所有节点。
示例:

输入: 1->2->6->3->4->5->6, val = 6输出: 1->2->3->4->5

代码

 /** * 删除链表中的节点 */ public static ListNode removeElements(ListNode head, int val) { if (head == null) { return null; } //定义前指针 是为了删除节点 ListNode pre = null; //定义next是为了指针后移 ListNode next; for (ListNode i = head; i != null; i = next) { next = i.next; if (i.val == val) { //这个判断说明头一个节点，就需要删除，因此头指针后移 if (head.equals(i)) { head = head.next; } //前节点next指向后节点 if (pre != null) { pre.next = i.next; } i.next = null; } else { pre = i; } } return head; }

3.3 奇偶链表

• 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
• 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
  示例 1:

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

示例 2:

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

说明:

• 应当保持奇数节点和偶数节点的相对顺序。
• 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。
  代码

 public static ListNode oddEvenList(ListNode head) { if (head == null) { return null; } ListNode odd = head; ListNode even = head.next; ListNode evenHead = head.next; while (odd.next != null && even.next != null) { odd.next = even.next; odd = odd.next; even.next = odd.next; even = even.next; } odd.next = evenHead; return head; }

3.4 回文链表

请判断一个链表是否为回文链表。
示例 1:

输入: 1->2输出: false

示例 2:

输入: 1->2->2->1输出: true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

 /** * 断一个链表是否为回文链表 * 输入: 1->2->2->1 * 输出: true */ public static boolean isPalindrome(ListNode head) { if (head == null || head.next == null) { return true; } ListNode reverseNode = null;//指向反转的链表 ListNode nomalNode;//指向后面后半截链表 if (head.next.next == null) { reverseNode = head; nomalNode = head.next; reverseNode.next = null; } else { //快慢指针找中间值 //顺便反转前半截链表 ListNode slow = head; ListNode fast = head; ListNode tempSlow; ListNode tempFast; while (fast.next != null && fast.next.next != null) { tempSlow = slow.next; tempFast = fast.next.next; slow.next = reverseNode; reverseNode = slow; slow = tempSlow; fast = tempFast; } tempSlow = slow.next; slow.next = reverseNode; reverseNode = slow; //考虑链表是奇数长度链表 if (fast.next == null) { reverseNode = reverseNode.next; } nomalNode = tempSlow; } //遍历后半截找不同 while (nomalNode != null && reverseNode != null) { if (nomalNode.val != reverseNode.val) { return false; } nomalNode = nomalNode.next; reverseNode = reverseNode.next; } return true;

3.5 小结

快慢指针：可以找环，可以找中间点，可以相差n个节点的链表

四 双链表

4.1 简介 - 双链表

4.1.1 定义

双链表以类似的方式工作，但还有一个引用字段，称为“prev”字段。有了这个额外的字段，您就能够知道当前结点的前一个结点。

4.1.2 结点结构

// Definition for doubly-linked list.class DoublyListNode { int val; DoublyListNode next, prev; DoublyListNode(int x) {val = x;}}

与单链接列表类似，我们将使用头结点来表示整个列表。

4.1.3 操作

与单链表类似，我们将介绍在双链表中如何访问数据、插入新结点或删除现有结点。

1. 我们不能在常量级的时间内访问随机位置。
2. 我们必须从头部遍历才能得到我们想要的第一个结点。
3. 在最坏的情况下，时间复杂度将是 O(N)，其中 N 是链表的长度。

4.2 添加操作 - 双链表

如果我们想在现有的结点 prev 之后插入一个新的结点 cur，我们可以将此过程分为两个步骤：

1. 链接 cur 与 prev 和 next，其中 next 是 prev 原始的下一个节点；

   
   

2. 用 cur 重新链接 prev 和 next。

   
   

4.3 删除操作 - 双链表

如果我们想从双链表中删除一个现有的结点 cur，我们可以简单地将它的前一个结点 prev 与下一个结点 next 链接起来。

与单链表不同，使用“prev”字段可以很容易地在常量时间内获得前一个结点。

因为我们不再需要遍历链表来获取前一个结点，所以时间和空间复杂度都是O(1)。

五、小结 - 链表

5.1 小结

5.1.1 回顾

让我们简要回顾一下单链表和双链表的表现。
它们在许多操作中是相似的。

1. 它们都无法在常量时间内随机访问数据
2. 它们都能够在 O(1) 时间内在给定结点之后或列表开头添加一个新结点。
3. 它们都能够在 O(1) 时间内删除第一个结点

但是删除给定结点(包括最后一个结点)时略有不同。

• 在单链表中，它无法获取给定结点的前一个结点，因此在删除给定结点之前我们必须花费 O(N) 时间来找出前一结点。
• 在双链表中，这会更容易，因为我们可以使用“prev”引用字段获取前一个结点。因此我们可以在 O(1) 时间内删除给定结点。

5.1.2 对照

这里我们提供链表和其他数据结构（包括数组，队列和栈）之间时间复杂度的比较：

• 如果你需要经常添加或删除结点，链表可能是一个不错的选择。
• 如果你需要经常按索引访问元素，数组可能是比链表更好的选择。

5.2 合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：

输入：1->2->4, 1->3->4输出：1->1->2->3->4->4

 /** * 合并两个有序链表 */ public static ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) { return l2; } if (l2 == null) { return l1; } ListNode temp1 = l1; ListNode temp2 = l2; ListNode mergeListNode; if (l1.val > l2.val) { mergeListNode = l2; temp2 = l2.next; } else { mergeListNode = l1; temp1 = l1.next; } ListNode mergeListNodePointer = mergeListNode; //每次循环只前进一个指针 while (temp1 != null && temp2 != null) { if (temp1.val > temp2.val) { mergeListNodePointer.next = temp2; mergeListNodePointer=mergeListNodePointer.next; temp2 = temp2.next; } else { mergeListNodePointer.next = temp1; mergeListNodePointer=mergeListNodePointer.next; temp1 = temp1.next; } } //将剩余的节点拼接起来 if (temp1 != null) { mergeListNodePointer.next = temp1; } if (temp2 != null) { mergeListNodePointer.next = temp2; } return mergeListNode; }

5.3 两数相加

参考

您还可以搜索:数据结构链表java代码,数据结构链表java,数据结构链表尾插法,数据结构链表实验报告,数据结构链表代码,数据结构链表的基本操作,数据结构链表的增删改查,数据结构链表定义,数据结构链表c语言实现,数据结构链表实验心得体会④