单链表
头结点：用来记录链表的基地址；
尾结点：指向的是一个空地址NULL；
插入、删除
- 数组在进行插入、删除操作时，为了保持内存数据的连续性，需要做大量的数据搬移，所以时间复杂度是O(n)；
- 链表中插入、删除操作时，并不需要为了保持内存的连续性而搬移节点，因为链表的存储空间本身就不是连续的；所以只需要考虑相邻节点的指针改变，对应的时间复杂度为O(1);
边界的问题：
针对链表的插入、删除操作，需要对插入第一个节点和删除最后一个节点的情况进行特殊处理；
插入操作
在空链表插入第一个节点
if(head == null){
head = new_node;
}
在其他位置插入节点
new_node.next = p.next; p.next = new_node;
删除链表的最后一个节点
if(head.next == null){
head = null;
}
删除链表中的其他节点
解决：哨兵节点
p.next = p.next.next;
- 引入哨兵节点，在任何时候，不管链表是不是空，head指针都会一直指向这个哨兵节点。我们也把这种有哨兵节点的链表叫带头节点；
- 引入哨兵节点统一了代码的逻辑实现，具体可以参考后面的删除节点问题。
查找
如果链表想要随机访问第k个元素，就没有数组那么高效了；因为链表中的数据并非连续存储的，所以无法像数组那样，根据首地址和下标，通过寻址公式就能直接计算出对应的内存地址，而是需要根据指针一个节点一个节点的依次遍历，直到找到相应的节点，所以时间复杂度为O(n)
循环链表
- 循环链表是特殊的单链表。单链表是尾结点指针指向空地址，表示最后的节点；而循环链表的尾结点指针指向链表的头节点。
- 著名问题：约瑟夫环（循环链表有n个节点，每次移除第m个节点，最终剩下的节点）
public int lastRemaining(int n, int m){
int res = 0;
for(int i = 2; i <= n; i++){
res = (res + m) % i;
}
return res;
}
双向链表
概念
单向链表只有一个方向，节点只有一个后续指针next指向后面的节点；双向链表支持两个方向，每个节点不止有一个后继指针next指向后面的节点，还有一个前驱指针prev指向前面的节点。
优势
双向链表在某些情况下的插入、删除操作要比单链表简单、高效
- 例如：删除给定指针指向的节点
- 单链表在指定节点的指针指向的位置插入或者删除的时间复杂度为O（1）。但是如果要删除指定的某个节点，需要知道其前驱节点，而单链表找到前驱节点需要从头节点开始遍历链表，直到p.next = q，所以时间复杂度为O（n）；
- 而双向链表中的节点已经保存前驱节点的指针，所以只需要时间复杂度为O（1）；
有序链表，双向链表的按值查询的效率更高
- 比如，我们可以记录上次查找的位置p，每次查询时，根据要查找的值与p的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。
应用
- Linkedhashmap的有序性就是通过双向链表实现；
- LRU算法；
- 判断回文链表；
- 将单链表变为双向链表。
练习
- 单链表反转
剑指 Offer II 024. 反转链表
剑指 Offer 24. 反转链表
class Solution {
public ListNode reverseList(ListNode head) {
// 固定格式
ListNode cur = head, pre = null;
while(cur != null){
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
}
- 链表中环的检测
剑指 Offer II 022. 链表中环的入口节点
142. 环形链表 II
141. 环形链表
这里的判断条件是fast != null && fast.next != null；因为允许节点指向空节点，但是不允许空节点本身有指向，所以fast = fast.next.next是正确的
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
while(slow != head){
slow = slow.next;
head = head.next;
}
return head;
}
}
return null;
}
}
- 求链表的中间节点
如果是奇数是中间节点，如果是偶数是后一个中间节点；例如：2,3,4,5返回的是4
public ListNode findMiddle(ListNode head){
ListNode fast = head, slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
如果是奇数是中间节点，如果是偶数是前一个中间节点；例如：2,3,4,5返回的是3
public ListNode findMiddle(ListNode head){
if(head == null){
return head;
}
ListNode fast = head, slow = head;
while(fast.next != null && fast.next.next != null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
- 删除链表倒数第n个节点
注意建立哨兵节点，主要是防止 p.next = p.next.next操作报错
19. 删除链表的倒数第 N 个结点
剑指 Offer II 021. 删除链表的倒数第 n 个结点
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode sentinel = new ListNode(0, head);
ListNode fast = head;
ListNode slow = sentinel;
while(fast != null){
if(n > 0){
n--;
}else{
slow = slow.next;
}
fast = fast.next;
}
slow.next = slow.next.next;
return sentinel.next;
}
}
2095. 删除链表的中间节点（如果是偶数，后一个为中间节点）
class Solution {
public ListNode deleteMiddle(ListNode head) {
ListNode sentinel = new ListNode(0, head);
ListNode pre = sentinel;
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
pre = slow;
slow = slow.next;
}
pre.next = pre.next.next;
return sentinel.next;
}
}
237. 删除链表中的节点
面试题 02.03. 删除中间节点
class Solution {
// 伪装成儿子、之后删除儿子
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}
剑指 Offer 18. 删除链表的节点
class Solution {
public ListNode deleteNode(ListNode head, int val) {
ListNode sentinel = new ListNode(0, head);
ListNode node = sentinel;
while(node != null){
if(node.next.val == val){
break;
}
node = node.next;
}
node.next = node.next.next;
return sentinel.next;
}
}
- 两个有序的链表合并
21. 合并两个有序链表
剑指 Offer II 078. 合并排序链表
剑指 Offer 25. 合并两个排序的链表
三种实现
- 在原有链表上合并（使用递归）
- 返回新建链表
- 使用优先队列处理多个有序链表
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 在原有链表上操作
if(l1 == null){
return l2;
}
if(l2 == null){
return l1;
}
if(l1.val < l2.val){
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}else{
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 新建链表合并
if(l1 == null){
return l2;
}
if(l2 == null){
return l1;
}
ListNode head = new ListNode();
ListNode node = head;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
node.next = new ListNode(l1.val);
node = node.next;
l1 = l1.next;
}else{
node.next = new ListNode(l2.val);
node = node.next;
l2 = l2.next;
}
}
if(l1 != null){
node.next = l1;
}
if(l2 != null){
node.next = l2;
}
return head.next;
}
}
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null){
return l2;
}
if(l2 == null){
return l1;
}
Queue<ListNode> queue = new PriorityQueue<>((o1, o2) -> (o1.val - o2.val));
queue.offer(l1);
queue.offer(l2);
ListNode head = new ListNode();
ListNode node = head;
while(!queue.isEmpty()){
ListNode temp = queue.poll();
node.next = temp;
node = node.next;
if(temp.next != null){
queue.offer(temp.next);
}
}
return head.next;
}
}
- 拓展
剑指 Offer II 026. 重排链表
class Solution {
public void reorderList(ListNode head) {
//寻找前一个中间节点
if(head == null){
return;
}
ListNode slow = head, fast = head;
while(fast.next != null && fast.next.next != null){
fast = fast.next.next;
slow = slow.next;
}
//cur就是后半段节点
ListNode cur = slow.next;
//断开前半段节点
slow.next = null;
//翻转链表
ListNode pre = null;
while(cur != null){
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
//合并链表
ListNode node = head;
while(head != null && pre != null){
ListNode l1 = node.next;
ListNode l2 = pre.next;
node.next = pre;
node = l1;
pre.next = node;
pre = l2;
}
}
}
剑指 Offer II 077. 链表排序（归并）
class Solution {
public ListNode sortList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode fast = head, slow = head;
// 指向的是前一个中间
while(fast.next != null && fast.next.next != null){
fast = fast.next.next;
slow = slow.next;
}
ListNode mid = slow.next;
slow.next = null;
// 前后半段
ListNode list1 = sortList(head);
ListNode list2 = sortList(mid);
return merge(list1, list2);
}
public ListNode merge(ListNode list1, ListNode list2){
ListNode cur = new ListNode();
ListNode node = cur;
while(list1 != null && list2 != null){
if(list1.val < list2.val){
node.next = list1;
list1 = list1.next;
}else{
node.next = list2;
list2 = list2.next;
}
node = node.next;
}
if(list1 != null){
node.next = list1;
}else if(list2 != null){
node.next = list2;
}
return cur.next;
}
}
25. K 个一组翻转链表（使用递归、相当于反转链表的进阶）
/**
* 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 reverseKGroup(ListNode head, int k) {
if(head == null){
return head;
}
//定位此组的后面的节点
ListNode position = head;
for(int i = 0; i < k; i++){
if(position == null){
return head;
}
position = position.next;
}
ListNode pre = null, cur = head;
while(cur != position){
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
// cur是剩余的head节点
head.next = reverseKGroup(cur, k);
return pre;
}
}
京公网安备 11010502036488号