精选算法面试 - 链表（反转）

李孟

关注

发布于: 2021 年 01 月 08 日

一.简介

挑选了几道常考的反转链表题，链表是通过指针将一组零散的内存串联在一起，反转充分了利用指针来操作。（不限语言，本文是 Java 示例）

二.示例

2.1 反转链表

反转一个单链表，例如把 1->2->3->null 反转 3->2->1->null 形式，指针反转，不仅仅是值的变化。

迭代

迭代的形式，按照一般思路先有一个指针指向前驱结点，每次都在移位前驱结点，这样把指针反转过来。

public void reverseList(ListNode head){  ListNode reList = null;  //前驱  ListNode prev = null;  //当前  ListNode curr = head;  while (curr != null){    //指向下一个结点    ListNode next = curr.getNext();    if(next == null){        reList = curr;    }    //当前结点指向前驱结点，例如 1-> null    curr.setNext(prev);    //前驱结点被赋值 1-> null    prev = curr;    // 2-> 3 如此进行迭代    curr = next; } return reList;}

复制代码

递归

public ListNode reverseList(ListNode head) {        return reverseList2(null,head);    }    //跟迭代类似，运用前驱结点，每次递归，把提前存储在内存中next ,这样累加前驱结点地址    ListNode reverseList2(ListNode prev,ListNode curr){        if(curr == null) return prev;        ListNode next = curr.next;        curr.next = prev;        return reverseList2(curr,next);    }

复制代码

2.2 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表，你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

迭代

因为从第一个结点开始反转，这样引入哨兵，不参与计算，站位好处理第一个结点，解决邻居依赖问题。

 public ListNode swapPairs(ListNode head) {        ListNode prev = new ListNode(0);        prev.next = head;        //前驱结点        ListNode p1 = prev;        ListNode p2 = null;        while(p1.next != null && p1.next.next != null){                        p2 = p1.next;//p2 等于 下一个结点  1->2->3->4            p1.next = p2.next;//这两步骤把第二结点，赋值到 0 -> 2            //1->3->4 跳过2结点，因为要反转，把2结点放到第一位            p2.next = p2.next.next;            //0->2->1->3->4 第一组反转完毕            p1.next.next = p2;            //赋值p1 因为要进入下一组            p1 = p2;        }        return prev.next;  }

复制代码

递归

public ListNode swapPairs(ListNode h) {    if (h == null || h.next == null) {        return h;    }        ListNode newHead = h.next;    //这个递归是要把 3 -> 4，反转 4-> 3 ,然后返回上层再处理第一组1->2的反转    h.next = swapPairs(newHead.next);    newHead.next = h;    return newHead;}

复制代码

2.3 k 个一组反转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例

给你这个链表：1->2->3->4->5。

当 k = 2 时，应当返回: 2->1->4->3->5。

当 k = 3 时，应当返回: 3->2->1->4->5。

结点列表每 k 个就反转，相当于把 2.2 两辆反转变形了。

因为从第一个结点开始反转，这样引入哨兵，不参与计算，站位好处理第一个结点，解决邻居依赖问题，这个难度比较大，得需要借助图形更加深理解。

public void reverseKGroup(int k){    ListNode hair = new ListNode(0);    //头结点    ListNode head2 = head;    hair.setNext(head2);    ListNode pre = hair;    while (head2 != null) {        ListNode tail = pre;        // 查看剩余部分长度是否大于等于 k        for (int i = 0; i < k; ++i) {            tail = tail.getNext();            if (tail == null) {                              break;            }        }        ListNode nex = tail.getNext();        //反转，k个结点        ListNode[] reverse = myReverse(head2, tail);        //已经反转完毕的，一组结点        head2 = reverse[0];        //一组结点的后继结点        tail = reverse[1];        // 把子链表重新接回原链表        pre.setNext(head2);        tail.setNext(nex);                //这个是处理下一组的结点        pre = tail;        head2 = tail.getNext();    }    return hair.getNext();}/** * 反转 */private ListNode[] myReverse(ListNode curr,ListNode tail){    ListNode prev = tail.next;    ListNode p = curr;    //反转完毕，地址相等的判定    while (prev != tail) {        ListNode nex = p.next;        p.next = prev;        prev = p;        p = nex;    }    return new ListNode[]{tail, curr};}