大厂算法和数据结构解析《大厂学院已结》

由于不必须按顺序存储，链表在插入的时候可以达到 O(1)的复杂度，比另一种线性表 —— 顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间，而顺序表相应的时间复杂度分别是 O(n) 和 O(1)。

链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。

反转一个单链表。

示例:

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

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

进阶:

你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

链表的节点结构ListNode已经定义好，我们发现，反转链表的过程，其实跟val没有关系，只要把每个节点的next指向之前的节点就可以了。

从代码实现上看，可以有迭代和递归两种形式。

假设存在链表 1→2→3→null，我们想要把它改成null←1←2←3。

我们只需要依次迭代节点遍历链表，在迭代过程中，将当前节点的 next 指针改为指向前一个元素就可以了。

代码如下：

public class ReverseLinkedList {

    public ListNode reverseList(ListNode head) {

        ListNode curr = head;

        ListNode prev = null;

        // 依次迭代遍历链表

        while (curr != null){

            ListNode tempNext = curr.next;

            curr.next = prev;

            prev = curr;

            curr = tempNext;

        }

        return prev;

    }

}

复杂度分析

时间复杂度：O(n)，假设 n 是链表的长度，时间复杂度是 O(n)。

空间复杂度：O(1)。

递归的核心，在于当前只考虑一个节点。剩下部分可以递归调用，直接返回一个反转好的链表，然后只要把当前节点再接上去就可以了。

假设链表为（长度为m）：

n1 → n2 → …→nk−1 →nk →nk+1 →…→nm → null

若我们遍历到了nk，那么认为剩余节点nk+1到nm 已经被反转。

n1 → n2 → …→nk−1 →nk → nk+1 ←…← nm ​

我们现在希望 nk+1 的下一个节点指向 nk，所以，应该有

nk+1.next = nk

代码如下：

public ListNode reverseList(ListNode head) {

    if (head == null || head.next == null){

        return head;

    }

    ListNode restHead = head.next;

    ListNode reversedRest = reverseList(restHead);    // 递归反转

    restHead.next = head;

    head.next = null;

    return reversedRest;

}

复杂度分析

时间复杂度：时间复杂度：O(n)，假设 n 是链表的长度，那么时间复杂度为 O(n)。

空间复杂度：O(n)，由于使用递归，将会使用隐式栈空间。递归深度可能会达到 n 层。

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

示例：

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

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

链表节点结构已经定义好，而且已经做了升序排列。现在我们需要分别遍历两个链表，然后依次比较，按从小到大的顺序生成新的链表就可以了。这其实就是”归并排序”的思路。

最简单的想法，就是逐个遍历两个链表中的节点，依次比对。

我们假设原链表为list1和list2。只要它们都不为空，就取出当前它们各自的头节点就行比较。值较小的那个结点选取出来，加入到结果链表中，并将对应原链表的头（head）指向下一个结点；而值较大的那个结点则保留，接下来继续做比对。

另外，为了让代码更加简洁，我们可以引入一个哨兵节点（sentinel），它的next指向结果链表的头结点，它的值设定为-1。

代码如下：

public class MergeTwoSortedLists {

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        //定义一个哨兵节点

        ListNode resultPrev = new ListNode(-1);

        ListNode prev = resultPrev;

        // 遍历两个链表

        while ( l1 != null && l2 != null ){

            if ( l1.val <= l2.val ){ prev.next="l1;" prev="l1;" l1="l1.next;" } else { l2="l2.next;" =="null)" ? : l1; return resultprev.next; }< code></=>

复杂度分析

时间复杂度：O(n + m) ，其中 n 和 m 分别为两个链表的长度。因为每次循环迭代中，l1 和 l2 只有一个元素会被放进合并链表中， 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的，因此总的时间复杂度为 O(n+m)。

空间复杂度：O(1)。我们只需要常数的空间存放若干变量。

用递归的方式同样可以实现上面的过程。

当两个链表都不为空时，我们需要比对当前两条链的头节点。取出较小的那个节点；而两条链其余的部分，可以递归调用，认为它们已经排好序。所以我们需要做的，就是把前面取出的那个节点，接到剩余排好序的链表头节点前。

代码如下：

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

    if ( l1 == null )

        return l2;

    else 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); l2; }< code></=>

复杂度分析

时间复杂度：O(n + m)，其中 nn 和 m 分别为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点（直到至少有一个链表为空），函数 mergeTwoList 至多只会递归调用每个节点一次。因此，时间复杂度取决于合并后的链表长度，即 O(n+m)。

空间复杂度：O(n + m)，其中 n 和 m 分别为两个链表的长度。递归调用 mergeTwoLists 函数时需要消耗栈空间，栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n+m 次，因此空间复杂度为 O(n+m)。

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

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

在链表中删除某个节点，其实就是将之前一个节点next，直接指向当前节点的后一个节点，相当于”跳过”了这个节点。

当然，真正意义上的删除，还应该回收节点本身占用的空间，进行内存管理。这一点在java中我们可以不考虑，直接由JVM的GC帮我们实现。

最简单的想法是，我们首先从头节点开始对链表进行一次遍历，得到链表的长度 L。

然后，我们再从头节点开始对链表进行一次遍历，当遍历到第 L-N+1 个节点时，它就是我们需要删除的倒数第N个节点。

这样，总共做两次遍历，我们就可以得到结果。

代码如下：

public class RemoveNthNodeFromEnd {

    public ListNode removeNthFromEnd(ListNode head, int n) {

        // 遍历链表，获取长度

int l = getLength(head);

        // 定义哑节点（哨兵）

        ListNode sentinel = new ListNode(-1);

        sentinel.next = head;

        // 再次遍历，找到倒数第N个

        ListNode curr = sentinel;

        for ( int i = 0; i < l - n; i++ ){

            curr = curr.next;

        }

        curr.next = curr.next.next;

        return sentinel.next;

    }

    // &#x5B9A;&#x4E49;&#x4E00;&#x4E2A;&#x83B7;&#x53D6;&#x94FE;&#x8868;&#x957F;&#x5EA6;&#x7684;&#x65B9;&#x6CD5;

    public static int getLength(ListNode head){

        int length = 0;

        while ( head != null ){

            length ++;

            head = head.next;

        }

        return length;

    }

}

复杂度分析

时间复杂度：O(L)，其中 L 是链表的长度。只用了两次遍历，是线性时间复杂度。

空间复杂度：O(1)。

另一个思路是利用栈数据结构。因为栈是”先进后出”的，所以我们可以在遍历链表的同时将所有节点依次入栈，然后再依次弹出。

这样，弹出栈的第 n 个节点就是需要删除的节点，并且目前栈顶的节点就是待删除节点的前驱节点。这样一来，删除操作就变得十分方便了。

代码如下：

public ListNode removeNthFromEnd(ListNode head, int n) {

    ListNode sentinel = new ListNode(-1);

    sentinel.next = head;

    // 定义栈

    Stack<listnode> stack = new Stack<>();

    ListNode curr = sentinel;

    // &#x904D;&#x5386;&#x94FE;&#x8868;&#xFF0C;&#x6240;&#x6709;&#x8282;&#x70B9;&#x5165;&#x6808;

    while ( curr != null ){

        stack.push(curr);

        curr = curr.next;

    }

    // &#x4F9D;&#x6B21;&#x5F39;&#x6808;&#xFF0C;&#x5F39;&#x51FA;N&#x4E2A;

    for ( int i = 0; i < n; i++ ){

        stack.pop();

    }

    stack.peek().next = stack.peek().next.next;

    return sentinel.next;

}</listnode>

复杂度分析

时间复杂度：O(L)，其中 L是链表的长度。我们压栈遍历了一次链表，弹栈遍历了N个节点，所以应该耗费O(L+N)时间。N

Original: https://www.cnblogs.com/itit9696/p/15284812.html
Author: cml46679910
Title: 大厂算法和数据结构解析《大厂学院已结》