5-链表题

链表反转

常见的解决方法分为递归和迭代两种
我们知道迭代是从前往后依次处理，直到循环到链尾；而递归恰恰相反，首先一直迭代到链尾也就是递归基判断的准则，然后再逐层返回处理到开头。总结来说，链表翻转操作的顺序对于迭代来说是从链头往链尾，而对于递归是从链尾往链头。下面我会用详细的图文来剖析其中实现的细节。

递归操作链表并不高效。和迭代解法相比，虽然时间复杂度都是 O(N)，但是迭代解法的空间复杂度是 O(1)，而递归解法需要堆栈，空间复杂度是 O(N)。所以递归操作链表可以作为对递归算法的练习或者拿去和小伙伴装逼，但是考虑效率的话还是使用迭代算法更好。

迭代

迭代的方式是从链头开始处理，如下图给定一个存放5个数的链表。

首先对于链表设置两个指针：

然后依次将旧链表上每一项添加在新链表的后面，然后新链表的头指针 NewH 移向新的链表头，如下图所示。此处需要注意，不可以上来立即将上图中 P->next 直接指向 NewH，这样存放2的地址就会被丢弃，后续链表保存的数据也随之无法访问。而是应该设置一个临时指针 tmp，先暂时指向 P->next 指向的地址空间，保存原链表后续数据。然后再让 P->next 指向 NewH，最后 P=tmp 就可以取回原链表的数据了，所有循环访问也可以继续展开下去。

红线就是：p.next = newHead;

指针继续向后移动，直到P指针指向NULL停止迭代。

最后一步：

非递归实现的程序

public ListNode reverseList(ListNode head) {  
    if (head == null || head.next == null) //链表为空或者仅1个数直接返回  
        return head;  
    ListNode p = head, newHead = null;  
    while (p != null) {         //一直迭代到链尾  
        ListNode tmp = p.next;  //暂存p下一个地址，防止变化指针指向后找不到后续的数  
        p.next = newHead;       //p->next指向前一个空间，和下面换了一下位置  
        newHead = p;           //新链表的头移动到p，扩长一步链表  
        p = tmp;              //p指向原始链表p指向的下一个空间  
    }  
    return newHead;  
}

递归解法

public ListNode reverseList(ListNode h) {
    if (h == null || h.next == null) //链表为空直接返回，而head.next为空是递归基
        return h;
    ListNode newHead = reverseList(h.next); //一直循环到链尾 
    h.next.next = h;                     //翻转链表的指向
    h.next = null;  //记得赋值NULL，防止链表错乱，避免两个节点互为next死循环
    return newHead;     //不论当前节点是啥，都返回原本链表的最后一个节点-》也就是反转后的头节点
  }

前面非递归方式是从前面数1开始往后依次处理，而递归方式则恰恰相反，它先循环找到最后面指向的数5，然后从5开始处理依次翻转整个链表。

第一种解释

第二种解释

首先指针H迭代到底如下图所示，并且设置一个新的指针作为翻转后的链表的头。由于整个链表翻转之后的头就是最后一个数，所以整个过程NewH指针一直指向存放5的地址空间。

然后 H 指针逐层返回的时候依次做下图的处理，将 H 指向的地址赋值给 H->next->next 指针，*4的 next 5的 next 指向4，4指向 null *

　　
继续返回操作：

　　
上图第一次如果没有将存放4空间的 next 指针赋值指向 NULL，第二次 H->next->next=H，就会将存放5的地址空间覆盖为3，这样链表一切都大乱了。接着逐层返回下去，直到对存放1的地址空间处理。

第三种解释

二、反转链表前 N 个节点

// 将链表的前 n 个节点反转（n <= 链表长度）
ListNode reverseN(ListNode head, int 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;
}

三、反转链表的一部分

递归魔法：反转单链表 | labuladong 的算法笔记
如何 K 个一组反转链表 | labuladong 的算法笔记

合并两个有序链表

思路1

可以模拟两个数组的合并，就是归并排序，比较第一个的大小，将小的放到结果链表中，然后接着比较，直到两个链表全部比较结束
如果有一个链表为空，就直接把另一个链表的剩余元素全部加到结果链表中即可，然后退出循环，具体步骤如图所示

public ListNode mergeTwoLists2(ListNode list1, ListNode list2) {  
    ListNode list3 = new ListNode(0);  
    ListNode ptr1 = list1;  
    ListNode ptr2 = list2;  
    ListNode ptr3 = list3;  
    while (true) {  
        if (ptr1.next == null) {  
            ptr3.next = ptr2;  
            break;  
        }  
  
        if (ptr2.next == null) {  
            ptr3.next = ptr2;  
            break;  
        }  
        if (list1.val < list2.val) {  
            ptr3.next = ptr1;  
            ptr3 = ptr3.next;  
            ptr1 = ptr1.next;  
        } else {  
            ptr3.next = ptr2;  
            ptr3 = ptr3.next;  
            ptr2 = ptr2.next;  
        }  
    }  
    return list3;

思路2

第二种解法其实主要的实现方式和上述的也一样，只不过是实现的方式不一致，第一种方法需要新开辟一个空间，用于存放结果。
其实在每步骤的操作都是一样的，将首位相比较，小的链接到下一个元素上，所以就可以采用递归的方法，具体如图所示

链表放入较小节点，不动，继续设置下一个, 归并排序的递归思想

public ListNode Merge(ListNode list1, ListNode list2) {  
    if (list1 == null) return list2;//注意鲁棒性  
    if (list2 == null) return list1;  
    if (list1.val <= list2.val) {  //利用归并排序的递归思想，将两个链表的较小节点链接起来  
        list1.next = Merge(list1.next, list2);  //如果list1当前节点小于list2当前节点，链表放入较小节点(不动，继续设置下一个)并将索引往后一个节点，与list2的原较大节点继续比较  
        return list1;  
    } else {  
        list2.next = Merge(list2.next, list1);  //如果list2当前节点小于list1当前节点，链表放入较小节点并将索引往后一个节点，与list1的原较大节点继续比较  
        return list2;  
    }  
}

160 . 相交链表

两个链表的第一个公共节点

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

空间复杂度 O (1) 时间复杂度为 O (n) O

这里使用图解的方式，解释比较巧妙的一种实现。

根据题目意思
如果两个链表相交，那么相交点之后的长度是相同的

我们需要做的事情是，让两个链表从同距离末尾同等距离的位置开始遍历。这个位置只能是较短链表的头结点位置。
为此，我们必须消除两个链表的长度差

指针 pA 指向 A 链表，指针 pB 指向 B 链表，依次往后遍历
如果 pA 到了末尾，则 pA = headB 继续遍历
如果 pB 到了末尾，则 pB = headA 继续遍历
比较长的链表指针指向较短链表 head 时，长度差就消除了
如此，只需要将最短链表遍历两次即可找到位置
听着可能有点绕，看图最直观，链表的题目最适合看图了

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode pA = headA, pB = headB;
    while (pA != pB) {
        pA = pA == null ? headB : pA.next;
        pB = pB == null ? headA : pB.next;
    }
    return pA;
}

其他理解

pA 走过的路径为 A 链+B 链
pB走过的路径为B链+A链
pA 和 pB 走过的长度都相同，都是 A 链和 B 链的长度之和，相当于将两条链从尾端对齐，如果相交，则会提前在相交点相遇，如果没有相交点，则会在最后相遇。

两个人速度一致，走过的路程一致。那么肯定会同一个时间点到达终点

其实就是让2个指针走一样的距离，消除步行差，那就一定可以一起走到相交点

若相交，链表 A： a+c, 链表 B : b+c.
a+c+b+c = b+c+a+c 。则会在公共处 c 起点相遇。若不相交，a +b = b+a 。因此相遇处是 NULL

解法二

先获得两个链表的长度，然后在较长的链表上先走若干步 (两链表长度之差)，接着同时在两个链表上遍历，找到的第一个相同的节点就是他们的第一个公共节点

/**  
 * 52.两个链表的第一个公共节点(2)  
 * 长链表先走n步，第一个相同的就是公共节点  
 * 时间复杂度（m+n）空间复杂度（不需要栈了，小）  
 */  
public ListNode findFirstCommonNode2(ListNode headA, ListNode headB) {  
    //统计链表A和链表B的长度  
    int lenA = length(headA), lenB = length(headB);  
  
    //如果节点长度不一样，节点多的先走，直到他们的长度一样为止  
    while (lenA != lenB) {  
        if (lenA > lenB) {  
            //如果链表A长，那么链表A先走  
            headA = headA.next;  
            lenA--;  
        } else {  
            //如果链表B长，那么链表B先走  
            headB = headB.next;  
            lenB--;  
        }  
    }  
  
    //然后开始比较，如果他俩不相等就一直往下走  
    while (headA != headB) {  
        headA = headA.next;  
        headB = headB.next;  
    }  
    //走到最后，最终会有两种可能，一种是headA为空，  
    //也就是说他们俩不相交。还有一种可能就是headA  
    //不为空，也就是说headA就是他们的交点  
    return headA;  
}

//统计链表的长度  
private int length(ListNode node) {  
    int length = 0;  
    while (node != null) {  
        node = node.next;  
        length++;  
    }  
    return length;  
}

回文链表

/**  
 * 234、回文链表 head = [1,2,2,1]  
 * 1.复制链表值到数组列表中。  
 * 2.使用双指针法判断是否为回文。  
 * 总的时间复杂度：O(2n)=O(n)  
 * 空间复杂度：O(n)  
 */public boolean isPalindrome(ListNode head) {  
    List<Integer> vals = new ArrayList<Integer>();  
  
    // 将链表的值复制到数组中  
    ListNode currentNode = head;  
    while (currentNode != null) {  
        vals.add(currentNode.val);  
        currentNode = currentNode.next;  
    }  
  
    // 使用双指针判断是否回文  
    int front = 0;  
    int back = vals.size() - 1;  
    while (front < back) {  
        if (!vals.get(front).equals(vals.get(back))) {  
            return false;  
        }  
        front++;  
        back--;  
    }  
    return true;  
}