基础算法—链表篇

链表的基础知识

链表的分类

单链表

代码

public class ListNode {
    // 结点的值
    int val;
    // 下一个结点
    ListNode next;
    // 节点的构造函数(无参)
    public ListNode() {}
    // 节点的构造函数(有一个参数)
    public ListNode(int val) {
        this.val = val;
    }
    // 节点的构造函数(有两个参数)
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

双链表

每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

双链表既可以向前查询也可以向后查询。

循环链表

顾名思义，就是链表首尾相连。循环链表可以用来解决约瑟夫环问题。

链表的存储方式

数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。

链表是通过指针域的指针链接在内存中各个节点。

所以链表中的节点在内存中不是连续分布的，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

链表的操作

删除节点

添加节点

反转节点

性能分析

虚拟头结点

链表的一大问题就是操作当前节点必须要找前一个节点才能操作。这就造成了，头结点的尴尬，因为头结点没有前一个节点了。

每次对应头结点的情况都要单独处理，所以使用虚拟头结点的技巧，就可以解决这个问题。

反转链表

相关题目

增删改查

203. 移除链表元素

707. 设计链表

19. 删除链表的倒数第 N 个结点

思路

删除链表的倒数第 N 个结点

160. 相交链表

思路

链表拼接

双指针

21. 合并两个有序链表

86. 分隔链表

思路

将链表拆成两个，一个链表中的值都小于X，另一个都大于X，然后进行合并。

23. 合并K个升序链表

思路

小根堆

24. 两两交换链表中的节点

思路

两两交换链表中的节点

快慢指针

876. 链表的中间结点

141. 环形链表

思路

环形链表

142. 环形链表 II

思路

环形链表

反转链表(递归)

递归魔法：反转单链表 :: labuladong的算法小抄 (gitee.io)

反转整个链表

ListNode reverse(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode last = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return last;
}

反转前 N 个节点

ListNode successor = null; // 后驱节点

// 反转以 head 为起点的 n 个节点，返回新的头结点
ListNode reverseN(ListNode head, int n) {
    if (n == 1) {
        // 记录第 n + 1 个节点
        successor = head.next;
        return head;
    }
    // 以 head.next 为起点，需要反转前 n - 1 个节点
    ListNode last = reverseN(head.next, n - 1);

    head.next.next = head;
    // 让反转之后的 head 节点和后面的节点连起来
    head.next = successor;
    return last;
}

反转链表的一部分

ListNode reverseBetween(ListNode head, int m, int n) {
    // base case
    if (m == 1) {
        return reverseN(head, n);
    }
    // 前进到反转的起点触发 base case
    head.next = reverseBetween(head.next, m - 1, n - 1);
    return head;
}

反转链表(迭代)

反转整个链表

ListNode reverse(ListNode a) {
    ListNode pre, cur, nxt;
    pre = null; cur = a; nxt = a;
    while (cur != null) {
        nxt = cur.next;
        cur.next = pre;
        pre = cur;
        cur = nxt;
    }
    // 返回反转后的头结点
    return pre;
}

反转区间 [a, b) 的元素，注意是左闭右开

ListNode reverse(ListNode a,ListNode b){
        ListNode pre=null,cur=a,temp=a;
        while(cur!=b){
            temp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }