赞
踩
定义
在计算机科学中,链表是数据元素的线性集合,其每个元素都指向下一个元素,元素存储上并不连续
In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next.
可以分类为
随机访问性能
根据 index 查找,时间复杂度 O ( n ) O(n) O(n)
插入或删除性能
根据单向链表的定义,首先定义一个存储 value 和 next 指针的类 Node,和一个描述头部节点的引用
public class SinglyLinkedList {
private Node head; // 头部节点
private static class Node { // 节点类
int value;
Node next;
public Node(int value, Node next) {
this.value = value;
this.next = next;
}
}
}
头部添加
public class SinglyLinkedList {
// ...
public void addFirst(int value) {
this.head = new Node(value, this.head);
}
}
while 遍历
public class SinglyLinkedList {
// ...
public void loop() {
Node curr = this.head;
while (curr != null) {
// 做一些事
curr = curr.next;
}
}
}
for 遍历
public class SinglyLinkedList {
// ...
public void loop() {
for (Node curr = this.head; curr != null; curr = curr.next) {
// 做一些事
}
}
}
/** * 遍历链表1 * * @param consumer 要执行的操作 */ public void loop1(Consumer<Integer> consumer) { Node p = head; while (p != null) { consumer.accept(p.value); p = p.next; } } /** * 遍历链表2 * * @param consumer 要执行的操作 */ public void loop2(Consumer<Integer> consumer) { for (Node p = head; p != null; p = p.next) { consumer.accept(p.value); } } public class TestSinglyLinkedList { private SinglyLinkedList getLinkedList() { SinglyLinkedList list = new SinglyLinkedList(); list.addLast(1); list.addLast(2); list.addLast(3); list.addLast(4); return list; } @Test @DisplayName("测试while遍历") public void test001() { SinglyLinkedList list = getLinkedList(); list.loop1(value -> { System.out.println("while:" + value); }); } @Test @DisplayName("测试for遍历") public void test002() { SinglyLinkedList list = getLinkedList(); list.loop1(value -> { System.out.println("for:" + value); }); } }
迭代器遍历
public class SinglyLinkedList implements Iterable<Integer> { // ... private class NodeIterator implements Iterator<Integer> { Node curr = head; public boolean hasNext() { return curr != null; } public Integer next() { int value = curr.value; curr = curr.next; return value; } } public Iterator<Integer> iterator() { return new NodeIterator(); } }
NodeIterator
要定义为非 static 内部类,是因为它与 SinglyLinkedList
实例相关,是对某个 SinglyLinkedList
实例的迭代递归遍历
public class SinglyLinkedList implements Iterable<Integer> { // 递归1 public void loop() { recursion(this.head); } private void recursion(Node curr) { if (curr == null) { return; } // 前面做些事 recursion(curr.next); // 后面做些事 } // 递归2 public void loop3(Consumer<Integer> before, Consumer<Integer> after) { recursion(head, before, after); } private void recursion(Node curr, Consumer<Integer> before, Consumer<Integer> after) { // 某个节点要进行的操作 if (curr == null) { return; } before.accept(curr.value); recursion(curr.next, before, after); after.accept(curr.value); } } public class TestSinglyLinkedList { @Test @DisplayName("测试递归遍历") public void test() { SinglyLinkedList list = getLinkedList(); list.loop3(value -> { System.out.println("before:" + value); }, value -> { System.out.println("after:" + value); }); } }
结果
已连接到地址为 ''127.0.0.1:9477',传输: '套接字'' 的目标虚拟机
before:1
before:2
before:3
before:4
after:4
after:3
after:2
after:1
已与地址为 ''127.0.0.1:9477',传输: '套接字'' 的目标虚拟机断开连接
进程已结束,退出代码为 0
尾部添加
public class SinglyLinkedList { // ... private Node findLast() { if (this.head == null) { return null; } Node curr; for (curr = this.head; curr.next != null; ) { curr = curr.next; } return curr; } public void addLast(int value) { Node last = findLast(); if (last == null) { addFirst(value); return; } last.next = new Node(value, null); } }
尾部添加多个
public class SinglyLinkedList { // ... public void addLast(int first, int... rest) { Node sublist = new Node(first, null); Node curr = sublist; for (int value : rest) { curr.next = new Node(value, null); curr = curr.next; } Node last = findLast(); if (last == null) { this.head = sublist; return; } last.next = sublist; } }
根据索引获取
public class SinglyLinkedList { // ... private Node findNode(int index) { int i = 0; for (Node curr = this.head; curr != null; curr = curr.next, i++) { if (index == i) { return curr; } } return null; } private IllegalArgumentException illegalIndex(int index) { return new IllegalArgumentException(String.format("index [%d] 不合法%n", index)); } public int get(int index) { Node node = findNode(index); if (node != null) { return node.value; } throw illegalIndex(index); } }
插入
public class SinglyLinkedList {
// ...
public void insert(int index, int value) {
if (index == 0) {
addFirst(value);
return;
}
Node prev = findNode(index - 1); // 找到上一个节点
if (prev == null) { // 找不到
throw illegalIndex(index);
}
prev.next = new Node(value, prev.next);
}
}
删除
public class SinglyLinkedList { // ... public void remove(int index) { if (index == 0) { if (this.head != null) { this.head = this.head.next; return; } else { throw illegalIndex(index); } } Node prev = findNode(index - 1); Node curr; if (prev != null && (curr = prev.next) != null) { prev.next = curr.next; } else { throw illegalIndex(index); } } }
观察之前单向链表的实现,发现每个方法内几乎都有判断是不是 head 这样的代码,能不能简化呢?
用一个不参与数据存储的特殊 Node 作为哨兵,它一般被称为哨兵或哑元,拥有哨兵节点的链表称为带头链表
public class SinglyLinkedListSentinel {
// ...
private Node head = new Node(Integer.MIN_VALUE, null);
}
加入哨兵节点后,代码会变得比较简单,先看几个工具方法
public class SinglyLinkedListSentinel { // ... // 根据索引获取节点 private Node findNode(int index) { int i = -1; for (Node curr = this.head; curr != null; curr = curr.next, i++) { if (i == index) { return curr; } } return null; } // 获取最后一个节点 private Node findLast() { Node curr; for (curr = this.head; curr.next != null; ) { curr = curr.next; } return curr; } }
这样,代码简化为
public class SinglyLinkedListSentinel { // ... public void addLast(int value) { Node last = findLast(); /* 改动前 if (last == null) { this.head = new Node(value, null); return; } */ last.next = new Node(value, null); } public void insert(int index, int value) { /* 改动前 if (index == 0) { this.head = new Node(value, this.head); return; } */ // index 传入 0 时,返回的是哨兵 Node prev = findNode(index - 1); if (prev != null) { prev.next = new Node(value, prev.next); } else { throw illegalIndex(index); } } public void remove(int index) { /* 改动前 if (index == 0) { if (this.head != null) { this.head = this.head.next; return; } else { throw illegalIndex(index); } } */ // index 传入 0 时,返回的是哨兵 Node prev = findNode(index - 1); Node curr; if (prev != null && (curr = prev.next) != null) { prev.next = curr.next; } else { throw illegalIndex(index); } } public void addFirst(int value) { /* 改动前 this.head = new Node(value, this.head); */ this.head.next = new Node(value, this.head.next); // 也可以视为 insert 的特例, 即 insert(0, value); } }
public class DoublyLinkedListSentinel implements Iterable<Integer> { private final Node head; private final Node tail; public DoublyLinkedListSentinel() { head = new Node(null, 666, null); tail = new Node(null, 888, null); head.next = tail; tail.prev = head; } private Node findNode(int index) { int i = -1; for (Node p = head; p != tail; p = p.next, i++) { if (i == index) { return p; } } return null; } public void addFirst(int value) { insert(0, value); } public void removeFirst() { remove(0); } public void addLast(int value) { Node prev = tail.prev; Node added = new Node(prev, value, tail); prev.next = added; tail.prev = added; } public void removeLast() { Node removed = tail.prev; if (removed == head) { throw illegalIndex(0); } Node prev = removed.prev; prev.next = tail; tail.prev = prev; } public void insert(int index, int value) { Node prev = findNode(index - 1); if (prev == null) { throw illegalIndex(index); } Node next = prev.next; Node inserted = new Node(prev, value, next); prev.next = inserted; next.prev = inserted; } public void remove(int index) { Node prev = findNode(index - 1); if (prev == null) { throw illegalIndex(index); } Node removed = prev.next; if (removed == tail) { throw illegalIndex(index); } Node next = removed.next; prev.next = next; next.prev = prev; } private IllegalArgumentException illegalIndex(int index) { return new IllegalArgumentException( String.format("index [%d] 不合法%n", index)); } @Override public Iterator<Integer> iterator() { return new Iterator<Integer>() { Node p = head.next; @Override public boolean hasNext() { return p != tail; } @Override public Integer next() { int value = p.value; p = p.next; return value; } }; } static class Node { Node prev; int value; Node next; public Node(Node prev, int value, Node next) { this.prev = prev; this.value = value; this.next = next; } } }
双向环形链表带哨兵,这时哨兵既作为头,也作为尾
参考实现
public class DoublyLinkedListSentinel implements Iterable<Integer> { @Override public Iterator<Integer> iterator() { return new Iterator<>() { Node p = sentinel.next; @Override public boolean hasNext() { return p != sentinel; } @Override public Integer next() { int value = p.value; p = p.next; return value; } }; } static class Node { Node prev; int value; Node next; public Node(Node prev, int value, Node next) { this.prev = prev; this.value = value; this.next = next; } } private final Node sentinel = new Node(null, -1, null); // 哨兵 public DoublyLinkedListSentinel() { sentinel.next = sentinel; sentinel.prev = sentinel; } /** * 添加到第一个 * @param value 待添加值 */ public void addFirst(int value) { Node next = sentinel.next; Node prev = sentinel; Node added = new Node(prev, value, next); prev.next = added; next.prev = added; } /** * 添加到最后一个 * @param value 待添加值 */ public void addLast(int value) { Node prev = sentinel.prev; Node next = sentinel; Node added = new Node(prev, value, next); prev.next = added; next.prev = added; } /** * 删除第一个 */ public void removeFirst() { Node removed = sentinel.next; if (removed == sentinel) { throw new IllegalArgumentException("非法"); } Node a = sentinel; Node b = removed.next; a.next = b; b.prev = a; } /** * 删除最后一个 */ public void removeLast() { Node removed = sentinel.prev; if (removed == sentinel) { throw new IllegalArgumentException("非法"); } Node a = removed.prev; Node b = sentinel; a.next = b; b.prev = a; } /** * 根据值删除节点 * <p>假定 value 在链表中作为 key, 有唯一性</p> * @param value 待删除值 */ public void removeByValue(int value) { Node removed = findNodeByValue(value); if (removed != null) { Node prev = removed.prev; Node next = removed.next; prev.next = next; next.prev = prev; } } private Node findNodeByValue(int value) { Node p = sentinel.next; while (p != sentinel) { if (p.value == value) { return p; } p = p.next; } return null; } }
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
输入:[1,2]
输出:[2,1]
输入:[]
输出:[]
方法1
构造一个新链表,从旧链表依次拿到每个节点,创建新节点添加至新链表头部,完成后新链表即是倒序的
public ListNode reverseList(ListNode o1) {
ListNode n1 = null;
ListNode p = o1;
while (p != null) {
n1 = new ListNode(p.val, n1);
p = p.next;
}
return n1;
}
评价:简单直白,就是得新创建节点对象
方法2
与方法1 类似,构造一个新链表,从旧链表头部移除节点,添加到新链表头部,完成后新链表即是倒序的,区别在于原题目未提供节点外层的容器类,这里提供一个,另外一个区别是并不去构造新节点
static class List { ListNode head; public List(ListNode head) { this.head = head; } public ListNode removeFirst(){ ListNode first = head; if (first != null) { head = first.next; } return first; } public void addFirst(ListNode first) { first.next = head; head = first; } }
代码
public ListNode reverseList(ListNode head) {
List list1 = new List(head);
List list2 = new List(null);
ListNode first;
while ((first = list1.removeFirst()) != null) {
list2.addFirst(first);
}
return list2.head;
}
评价:更加面向对象,如果实际写代码而非刷题,更多会这么做
方法3
递归,在归时让 5 → 4 5 \rightarrow 4 5→4, 4 → 3 4 \rightarrow 3 4→3 …
首先,写一个递归方法,返回值用来拿到最后一个节点
public ListNode reverseList(ListNode p) {
if (p == null || p.next == null) { // 不足两个节点
return p; // 最后一个节点
}
ListNode last = reverseList(p.next);
return last;
}
可以先测试一下
ListNode o5 = new ListNode(5, null);
ListNode o4 = new ListNode(4, o5);
ListNode o3 = new ListNode(3, o4);
ListNode o2 = new ListNode(2, o3);
ListNode o1 = new ListNode(1, o2);
ListNode n1 = new E01Leetcode206().reverseList(o1);
System.out.println(n1);
会打印
[5]
下面为伪码调用过程,假设节点分别是 1 → 2 → 3 → 4 → 5 → n u l l 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null 1→2→3→4→5→null,先忽略返回值
reverseList(ListNode p = 1) { reverseList(ListNode p = 2) { reverseList(ListNode p = 3) { reverseList(ListNode p = 4) { reverseList(ListNode p = 5) { if (p == null || p.next == null) { return p; // 返回5 } } // 此时p是4, p.next是5 } // 此时p是3, p.next是4 } // 此时p是2, p.next是3 } // 此时p是1, p.next是2 }
接下来,从 p = 4 开始,要让 5 → 4 5 \rightarrow 4 5→4, 4 → 3 4 \rightarrow 3 4→3 …
reverseList(ListNode p = 1) { reverseList(ListNode p = 2) { reverseList(ListNode p = 3) { reverseList(ListNode p = 4) { reverseList(ListNode p = 5) { if (p == null || p.next == null) { return p; // 返回5 } } // 此时p是4, p.next是5, 要让5指向4,代码写成 p.next.next=p // 还要注意4要指向 null, 否则就死链了 } // 此时p是3, p.next是4 } // 此时p是2, p.next是3 } // 此时p是1, p.next是2 }
动画演示:
最终代码为:
public ListNode reverseList(ListNode p) {
if (p == null || p.next == null) { // 不足两个节点
return p; // 最后一个节点
}
ListNode last = reverseList(p.next);
p.next.next = p;
p.next = null;
return last;
}
Q:为啥不能在递的过程中倒序?
A:比如
评价:单向链表没有 prev 指针,但利用递归的特性【记住了】链表每次调用时相邻两个节点是谁
方法4
从链表每次拿到第二个节点,将其从链表断开,插入头部,直至它为 null 结束
设置指针 o1(旧头)、n1(新头)、o2(旧老二),分别指向第一,第一,第二节点 n 1 o 1 1 → o 2 2 → 3 → 4 → 5 → n u l l \frac{n1 \ o1}{1} \rightarrow \frac{o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null 1n1 o1→2o2→3→4→5→null
将 o2 节点从链表断开,即 o1 节点指向第三节点 n 1 o 1 1 → 3 → 4 → 5 → n u l l \frac{n1 \ o1}{1} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null 1n1 o1→3→4→5→null , o 2 2 \frac{o2}{2} 2o2
o2 节点链入链表头部,即 o 2 2 → n 1 o 1 1 → 3 → 4 → 5 → n u l l \frac{o2}{2} \rightarrow \frac{n1 \ o1}{1} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null 2o2→1n1 o1→3→4→5→null
n1 指向 o2 n 1 o 2 2 → o 1 1 → 3 → 4 → 5 → n u l l \frac{n1 \ o2}{2} \rightarrow \frac{o1}{1} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null 2n1 o2→1o1→3→4→5→null
o2 指向 o1 的下一个节点,即 n 1 2 → o 1 1 → o 2 3 → 4 → 5 → n u l l \frac{n1}{2} \rightarrow \frac{o1}{1} \rightarrow \frac{o2}{3} \rightarrow 4 \rightarrow 5 \rightarrow null 2n1→1o1→3o2→4→5→null
重复以上 2∼5步,直到 o2 指向 null
还应当考虑边界条件,即链表中不满两个元素时,无需走以上逻辑
动图:
动画演示中其实省略了一个tmp变量,这个tmp变量会将cur的下一个节点保存起来,考虑到一张动画放太多变量会很混乱,所以我就没加了,具体详细执行过程,请点击下面的幻灯片查看。
参考答案
public ListNode reverseList(ListNode o1) {
if (o1 == null || o1.next == null) { // 不足两个节点
return o1;
}
ListNode o2 = o1.next;
ListNode n1 = o1;
while (o2 != null) {
o1.next = o2.next;
o2.next = n1;
n1 = o2;
o2 = o1.next;
}
return n1;
}
例如
输入:head = [1,2,6,3,6], val = 6
输出:[1,2,3]
输入:head = [], val = 1
输出:[]
输入:head = [7,7,7,7], val = 7
输出:[]
方法1
public ListNode removeElements(ListNode head, int val) {
ListNode sentinel = new ListNode(-1, head);
ListNode p1 = sentinel;
ListNode p2;
while ((p2 = p1.next) != null) {
if (p2.val == val) {
p1.next = p2.next;
} else {
p1 = p1.next;
}
}
return sentinel.next;
}
方法2
递归图解
代码:
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head==null)
return null;
head.next=removeElements(head.next,val);
if(head.val==val){
return head.next;
}else{
return head;
}
}
}
例如
输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807.
输入:l1 = [0], l2 = [0]
输出:[0]
输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出:[8,9,9,9,0,0,0,1]
思路:
图解:
代码
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode pre = new ListNode(0); ListNode cur = pre; int carry = 0; while(l1 != null || l2 != null) { int x = l1 == null ? 0 : l1.val; int y = l2 == null ? 0 : l2.val; int sum = x + y + carry; carry = sum / 10; sum = sum % 10; cur.next = new ListNode(sum); cur = cur.next; if(l1 != null) l1 = l1.next; if(l2 != null) l2 = l2.next; } if(carry == 1) { cur.next = new ListNode(carry); } return pre.next; } }
例如
输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]
输入:head = [1], n = 1
输出:[]
输入:head = [1,2], n = 1
输出:[1]
解题思路:
画解
代码
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { //通过快慢指针来解决,类似于你要删除中间元素的题 public ListNode removeNthFromEnd(ListNode head, int n) { //定义一个伪节点,用于返回结果 ListNode dumpy = new ListNode(0); dumpy.next = head; //定义一个快指针,指向伪节点,用于遍历链表 ListNode prev = dumpy; //定一个慢指针, ListNode tail = dumpy; //让快指针先移动 n 步 while(n >0){ prev = prev.next; n--; } //只要快指针不指向空,就继续循环 while(prev.next !=null){ //让快慢指针同时移动 tail = tail.next; prev = prev.next; } //这时慢指针移动到的位置就是,要删除节点的前一个节点 //所以只要删除当前节点的下一个节点 tail.next = tail.next.next; //返回为指针指向的头节点 return dumpy.next; } }
例如
输入:head = [1,1,2]
输出:[1,2]
输入:head = [1,1,2,3,3]
输出:[1,2,3]
注意:重复元素保留一个
方法1
图解:
代码
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode deleteDuplicates(ListNode head) { ListNode cur = head; while(cur != null && cur.next != null) { if(cur.val == cur.next.val) { cur.next = cur.next.next; } else { cur = cur.next; } } return head; } }
方法2
主要思想:
链表具有天然的递归性,链表看成其头节点后挂接一个更短的链表,这个更短的链表看成其头节点后面挂接一个更更短的链表,依次类推。
因此本题可以按照如下步骤处理:
删除更短链表中所有重复的元素;
判断原链表的头节点的值是否等于经过第 1 步处理后的更短链表头节点的值;
若相等,则返回更短的链表;
否则,将更短的链表挂接在原链表的头节点的后面,再返回。
边界条件
代码:
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (null == head || null == head.next) {
return head;
}
head.next = deleteDuplicates(head.next);
return head.val == head.next.val ? head.next : head;
}
}
例如
输入:head = [1,2,3,3,4,4,5]
输出:[1,2,5]
输入:head = [1,1,1,2,3]
输出:[2,3]
注意:重复元素一个不留
方法1
代码
class Solution { public ListNode deleteDuplicates(ListNode head) { if (head == null || head.next == null) { return head; } if (head.val == head.next.val) { while (head != null && head.next != null && head.val == head.next.val) { head = head.next; } return deleteDuplicates(head.next); } else { head.next = deleteDuplicates(head.next); return head; } } }
方法2
p1 是待删除的上一个节点,每次循环对比 p2、p3 的值
p1 p2 p3 s, 1, 1, 1, 2, 3, null p1 p2 p3 s, 1, 1, 1, 2, 3, null p1 p2 p3 s, 1, 1, 1, 2, 3, null p1 p3 s, 2, 3, null p1 p2 p3 s, 2, 3, null p1 p2 p3 s, 2, 3, null
代码
/** * 删除链表中的重复元素。 * <p> * 本方法通过创建一个虚拟节点s来简化链表操作,避免处理头节点为空或只有一个节点的特殊情况。 * 使用三个指针p1, p2, p3来遍历链表,其中p1用于标记当前检查到的位置,p2和p3用于比较是否存在重复元素。 * 如果发现重复元素,p1将直接指向重复元素后的第一个不重复元素,从而实现删除重复元素的功能。 * <p> * 时间复杂度:O(n),其中n是链表中的节点数。需要遍历链表中的每个节点一次。 * 空间复杂度:O(1),只需要常数的空间存储几个指针变量。 * * @param head 链表的头节点 * @return 删除重复元素后的链表的头节点 */ // 方法2 public ListNode deleteDuplicates(ListNode head) { // 处理链表为空或只有一个节点的情况 if (head == null || head.next == null) { return head; } // 创建一个虚拟节点s,将其next指向头节点,简化链表操作 ListNode s = new ListNode(-1, head); ListNode p1 = s; ListNode p2, p3; // 使用三个指针遍历链表,p2和p3用于比较是否存在重复元素 while ((p2 = p1.next) != null && (p3 = p2.next) != null) { // 如果p2和p3的值相同,表示存在重复元素 if (p2.val == p3.val) { // 移动p3直到找到第一个不重复的元素 while ((p3 = p3.next) != null && p3.val == p2.val) { } // 将p1的next指向不重复元素,实现删除重复元素的功能 // p3 找到了不重复的值 p1.next = p3; } else { // 如果p2和p3的值不同,移动p1到下一个位置 p1 = p1.next; } } // 返回删除重复元素后的链表的头节点 return s.next; }
例如
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
输入:l1 = [], l2 = []
输出:[]
输入:l1 = [], l2 = [0]
输出:[0]
方法1
p1
1 3 8 9 null
p2
2 4 null
p
s null
代码
public ListNode mergeTwoLists(ListNode p1, ListNode p2) { ListNode s = new ListNode(-1, null); ListNode p = s; while (p1 != null && p2 != null) { if (p1.val < p2.val) { p.next = p1; p1 = p1.next; } else { p.next = p2; p2 = p2.next; } p = p.next; } if (p1 != null) { p.next = p1; } if (p2 != null) { p.next = p2; } return s.next; }
方法2
递归函数应该返回
递归主要想清楚一下几点
1.这个问题的子问题是什么。
2.当前层要干什么事情。
3.递归出口。
图解
代码
class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) { return l2; } else if (l2 == null) { return l1; } else if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; } } }
例如
输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下:
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
方法1
利用堆做排序
合并两个链表我们可以用if-else做判断,但是k个链接,用if-else,这就没法写了。
这时候我们需要一种辅助数据结构-堆,有了堆这个数据结构,难度等级是困难的题目,瞬间变成简单了。
我们把三个链表一股脑的全放到堆里面
1->4->5
1->3->4
2->6
然后由堆
根据节点的val
自动排好序
这是一个小根堆,我们只需要每次输出堆顶的元素,直到整个堆为空即可。
执行过程如下:
代码
class Solution { public ListNode mergeKLists(ListNode[] lists) { if(lists==null || lists.length==0) { return null; } //创建一个堆,并设置元素的排序方式 PriorityQueue<ListNode> queue = new PriorityQueue(new Comparator<ListNode>() { public int compare(ListNode o1, ListNode o2) { return (o1.val - o2.val); } }); //遍历链表数组,然后将每个链表的每个节点都放入堆中 for(int i=0;i<lists.length;i++) { while(lists[i] != null) { queue.add(lists[i]); lists[i] = lists[i].next; } } ListNode dummy = new ListNode(-1); ListNode head = dummy; //从堆中不断取出元素,并将取出的元素串联起来 while( !queue.isEmpty() ) { dummy.next = queue.poll(); dummy = dummy.next; } dummy.next = null; return head.next; } }
堆排序的优化
首先看下下面这张图
4个链表中的最小值,一定来自黄色的部分,黄色的部分就是一个小根堆。
这个堆的元素个数是k个,也就是图中的4个。
我们建立完k个大小的堆后,就不断的从堆中获取节点,如果获取到的节点不为空,即还有下一个节点,那么就将下一个节点放到堆中。利用这个特点我们就可以优化空间了,将原先的O(N)的空间复杂度优化到O(k)。
这种场景就好像就是4个售票窗口(图中只有一个窗口,嗯,脑补下剩下三个。。。),4排队伍在排队买票,但是只有一个工作人员,第一个人拿到票后,后面的人往前走,工作人员继续处理。
动画
代码
class Solution { public ListNode mergeKLists(ListNode[] lists) { if(lists==null || lists.length==0) { return null; } //创建一个小根堆,并定义好排序函数 PriorityQueue<ListNode> queue = new PriorityQueue(new Comparator<ListNode>() { public int compare(ListNode o1, ListNode o2) { return (o1.val - o2.val); } }); ListNode dummy = new ListNode(-1); ListNode cur = dummy; //这里跟上一版不一样,不再是一股脑全部放到堆中 //而是只把k个链表的第一个节点放入到堆中 for(int i=0;i<lists.length;i++) { ListNode head = lists[i]; if(head!=null) { queue.add(head); } } //之后不断从堆中取出节点,如果这个节点还有下一个节点, //就将下个节点也放入堆中 while(queue.size()>0) { ListNode node = queue.poll(); cur.next = node; cur = cur.next; if(node.next!=null) { queue.add(node.next); } } cur.next = null; return dummy.next; } }
例如
输入:[1,2,3,4,5]
输出:此列表中的结点 3 (序列化形式:[3,4,5])
输入:[1,2,3,4,5,6]
输出:此列表中的结点 4 (序列化形式:[4,5,6])
解法:快慢指针,快指针一次走两步,慢指针一次走一步,当快指针到链表结尾时,慢指针恰好走到链表的一半
public ListNode middleNode(ListNode head) {
ListNode p1 = head; // 慢指针,中间点
ListNode p2 = head; // 快指针
while (p2 != null && p2.next != null) {
p1 = p1.next;
p2 = p2.next;
p2 = p2.next;
}
return p1;
}
所谓回文指正着读、反着读,结果一样,例如
[1,2,2,1]
[1,2,3,2,1]
它们都是回文链表,不是回文的例子
[1,2,3,1] --反过来--> [1,3,2,1]
/* 步骤1. 找中间点 步骤2. 中间点后半个链表反转 步骤3. 反转后链表与原链表逐一比较 */ public boolean isPalindrome(ListNode head) { ListNode middle = middle(head); ListNode newHead = reverse(middle); while (newHead != null) { if (newHead.val != head.val) { return false; } newHead = newHead.next; head = head.next; } return true; } private ListNode reverse(ListNode o1) { ListNode n1 = null; while (o1 != null) { ListNode o2 = o1.next; o1.next = n1; n1 = o1; o1 = o2; } return n1; } private ListNode middle(ListNode head) { ListNode p1 = head; // 慢 ListNode p2 = head; // 快 while (p2 != null && p2.next != null) { p1 = p1.next; p2 = p2.next.next; } return p1; }
优化后解法
public boolean isPalindrome(ListNode h1) { if (h1 == null || h1.next == null) { return true; } ListNode p1 = h1; // 慢指针,中间点 ListNode p2 = h1; // 快指针 ListNode n1 = null; // 新头 ListNode o1 = h1; // 旧头 // 快慢指针找中间点 while (p2 != null && p2.next != null) { p1 = p1.next; p2 = p2.next.next; // 反转前半部分 o1.next = n1; n1 = o1; o1 = p1; } if (p2 != null) { // 节点数为奇数 p1 = p1.next; } // 同步比较新头和后半部分 while (n1 != null) { if (n1.val != p1.val) { return false; } p1 = p1.next; n1 = n1.next; } return true; }
本题以及下题,实际是 Floyd’s Tortoise and Hare Algorithm (Floyd 龟兔赛跑算法)
如果链表上存在环,那么在环上以不同速度前进的两个指针必定会在某个时刻相遇。算法分为两个阶段
参考代码
public boolean hasCycle(ListNode head) {
ListNode h = head; // 兔
ListNode t = head; // 龟
while (h != null && h.next != null) {
t = t.next;
h = h.next.next;
if(h == t){
return true;
}
}
return false;
}
双指针的第一次相遇:
第一种结果: fast 指针走过链表末端,说明链表无环,此时直接返回 null。
如果链表存在环,则双指针一定会相遇。因为每走 1 轮,fast 与 slow 的间距 +1,fast 一定会追上 slow 。
第二种结果: 当fast == slow时, 两指针在环中第一次相遇。下面分析此时 fast 与 slow 走过的步数关系:
设链表共有 a+b 个节点,其中 链表头部到链表入口 有 a 个节点(不计链表入口节点), 链表环 有 b 个节点(这里需要注意,a 和 b 是未知数,例如图解上链表 a=4 , b=5);设两指针分别走了 f,s 步,则有:
将以上两式相减得到 f=2nb,s=nb,即 fast 和 slow 指针分别走了 2n,n 个环的周长。
接下来该怎么做呢?
如果让指针从链表头部一直向前走并统计步数k,那么所有 走到链表入口节点时的步数 是:k=a+nb ,即先走 a 步到入口节点,之后每绕 1 圈环( b 步)都会再次到入口节点。而目前 slow 指针走了 nb 步。因此,我们只要想办法让 slow 再走 a 步停下来,就可以到环的入口。
但是我们不知道 a 的值,该怎么办?依然是使用双指针法。考虑构建一个指针,此指针需要有以下性质:此指针和 slow 一起向前走 a 步后,两者在入口节点重合。那么从哪里走到入口节点需要 a 步?答案是链表头节点head。
双指针第二次相遇:
图示
参考代码(找到环入口)
public class Solution { public ListNode detectCycle(ListNode head) { ListNode fast = head, slow = head; while (true) { if (fast == null || fast.next == null) return null; fast = fast.next.next; slow = slow.next; if (fast == slow) break; } fast = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return fast; } }
原题叫做相交链表,个人觉得用共尾链表更形象些,此题更像是一道脑筋急转弯
例如,下图的两个链表 [1, 2, 4, 5] 与 [3, 4, 5] 它们中 [4, 5] 是相同的,此时应返回节点 4
非共尾的情况,如下图所示,此时返回 null
思路,称两个链表为 a=[1, 2, 4, 5],b=[3, 4, 5],图中用 N 代表 null
1 2 4 5 N 3 4 5 N
3 4 5 N 1 2 4 5 N
如果两个链表长度相同,则可以更早找到目标,例如 a=[1, 4, 5],b=[3, 4, 5],第一次出现 4 时,即可返回
1 4 5 N 3 4 5 N
3 4 5 N 1 4 5 N
如果是非共尾的情况,如 a=[1, 2, 4],b=[3, 5],可以看到,唯一相等的情况,是遍历到最后那个 N 此时退出循环
1 2 4 N 3 5 N
3 5 N 1 2 4 N
代码
public ListNode getIntersectionNode(ListNode a, ListNode b) { ListNode p1 = a; ListNode p2 = b; while (true) { if (p1 == p2) { return p1; } if (p1 == null) { p1 = b; } else { p1 = p1.next; } if (p2 == null) { p2 = a; } else { p2 = p2.next; } } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。