【算法】如何反转一个单链表？如何两两反转？

梦里梦外; 2022-08-20 11:11 24阅读 0赞

> 如何反转单链表？如何使用较少的遍历次数完成单链表的反转？

## 问题一、反转单链表 ##

题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

![这里写图片描述][20170802132730680]

链表结点定义如下，这里使用的是Java描述：

public class ListNode {
        
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

### 思路 ###

如何把一个单链表进行反转？

*  **方法1**：将单链表储存为数组，然后按照数组的索引逆序进行反转。
 *  **方法2**：用头插法新建链表。我们知道创建链表的两种方式：**头插法**和**尾插法**，头结点插入法形成的链表是和输入顺序相反的，尾节点插入法形成的链表是和输入顺序相同的，所以其中一种方法是，遍历原链表，然后用原链表的输出元素顺序用头结点插入法新建链表，这样新建的链表就是反转后的链表。
 *  **方法3**：就地反转链表。使用3个指针遍历单链表，逐个链接点进行反转。

#### **1、借助数组逆序反转** ####

由于题目并没有要求必须原地反转，因此可以借助外部空间实现。这里可以将单链表储存为数组，然后按照数组的索引逆序进行反转。但是，**此方式比较浪费空间，而且需要两次遍历，效率不占优势**。

/**
     * 使用数组拷贝的方式反转单链表
     */
    public static ListNode reverseList1(ListNode head){
        if(head == null) return null;
    
        //转移到数组存储(这里用ArrayList方便些)
        List<ListNode> nodeList = new ArrayList<ListNode>();
        while (head != null) {
            nodeList.add(head);
            head = head.next;
        }
    
        int startIndex = nodeList.size() - 1;
        for (int i = startIndex; i >= 0; i--) {
            ListNode node = nodeList.get(i);
            if (i == 0) {
                node.next = null;
            } else {
                node.next = nodeList.get(i - 1);
            }
        }
        // 现在头结点是原来的尾节点
        head = nodeList.get(startIndex);
        return head;
    }

#### **2、头插法新建链表来反转** ####

这个方法和第一个借助数组一样，需要额外一倍的空间来存储生成的新链表

/**
     * 头插法建立新链表，达到反转目的
     */
    public static ListNode reverseList2(ListNode head){
        if(head == null) return null;
    
        ListNode previous = null;   //记录上个节点
        ListNode newHead = null;    //头插法的新头节点
    
        while(head != null){
            newHead = new ListNode(head.val);   //新建头结点
            newHead.next = previous;
    
            previous = newHead;
            head = head.next;   //下一个节点
        }
        return newHead;
    }

#### **3、三个指针就地反转** ####

使用三个指针指向：当前节点A，下个节点B，以及下下个节点C。

遍历时，如下首先记录下下个节点C，然后节点B的指针断开并指向A。然后移动进入下一组。

A -> B -> C ->D -> E

**A <- B** 、 **C** \->D -> E

整个过程只需遍历链表一次，效率提高不少，且需要的外部空间也较第一种方法要少很多，实现代码如下：

/**
     * 使用三个指针原地反转单链表
     */
    public static ListNode reverseList(ListNode head){
        if(head == null) return null;
    
        ListNode a = head;      //当前节点A
        ListNode b = head.next; //下个节点B
        ListNode temp;          //下下个节点C
    
        //头结点的指针先清空
        head.next = null;
    
        //有可能链表只有一个节点，所以需要看b是否为null
        while(b != null){
            temp = b.next;  // 记录C节点
            b.next = a;     // a->b 反向
    
            if(temp == null){
                break;
            }
            a = b;      //移动到下一个节点
            b = temp;
        }
        return b == null ? a : b;
    }

### 单元测试 ###

测试代码如下：

public class Test {
        
    
        public static void main(String[] args) {
            ListNode a1 = new ListNode(5);
            ListNode a2 = new ListNode(4);
            ListNode a3 = new ListNode(30);
            ListNode a4 = new ListNode(78);
            ListNode a5 = new ListNode(99);
    
            a1.next = a2;
            a2.next = a3;
            a3.next = a4;
            a4.next = a5;
    
            //反转单链表
            ListNode node = reverseList(a1);
    
            //打印输出结果
            while (node != null){
                System.out.print(node.val);
                node = node.next;
                System.out.print(node != null ? "->" : "");
            }
        }
    }

## 问题二、单链表两两反转 ##

一个链表：`a->b->c->d->e`  
每两个元素进行反转：`b->a->d->c->e`  
输入：链表头指针  
输出：反转后的链表头指针  
要求：**不新建节点**

### 解答 ###

仿照前面的单链表反转，我们最少需要三个指针： current，next， nextNext。  
　　  
分析：我们需要两个“指针”指着当前要反转的两个值current和next。两两反转后，我们还需要记录下一个的值，即反转A和B后， 需要记录 C 值，我们才能够不断向下走，直到到达链表末端。所以，需要另一个指向下一个值的“指针”，即nextNext。反转以后，A的下一个是C， **但是，实际上，A的下一个应该是D**，所以，每次反转时，我们需要更新前一个值的下一个值，也就是说把 A -> C 改成 A -> D，所以需要prev指针。所以，要完成这个操作，我们总共需要4个“指针”。具体看代码：  
　　  
所以最终我们一共需要分析四个指针： prev，current，next， nextNext。

/**
     * 单链表两两反转
     *
     *      已知一个链表：a->b->c->d->e
     * 每两个元素进行反转：b->a->d->c->e
     */
    public static ListNode reversePairedList(ListNode head){
        if(head == null) return null;
    
        ListNode a = head;          //当前节点A
        ListNode b = head.next;     //下个节点B
        ListNode temp;              //下下个节点C
        ListNode previous = null;   //上一组的尾指针，在下一组反转后需要改变
        ListNode newHead = b == null ? a : b;
    
        while(b != null){
            temp = b.next;  // 记录C节点
            b.next = a;     // a->b 反向
            a.next = temp;
            if(previous != null){
                previous.next = b;
            }
    
            if(temp == null){
                break;
            }
            previous = a;
            a = temp;       //移动到下一组
            b = temp.next;
        }
        return newHead;
    }

## 参考资料 ##

*  [看图理解单链表的反转][Link 1]
 *  [算法学习之数据结构之单链表反转，两两反转][Link 2]
 *  [单链表的建立(C语言)：头插法和尾插法建立单链表][C]
 *  [蚂蚁金服在线笔试题 - 链表两两反转][-]
 *  [算法题：反转单链表][Link 3]

[20170802132730680]: /images/20220731/f3b39c31623546ecb1b6dcb61cc2d03f.png
[Link 1]: http://blog.csdn.net/feliciafay/article/details/6841115
[Link 2]: http://blog.csdn.net/lufeng20/article/details/7959973
[C]: http://c.biancheng.net/cpp/html/2671.html
[-]: https://hwdlei.github.io/%E7%AC%94%E8%AF%95%E9%9D%A2%E8%AF%95/2016/10/20/list-revert/
[Link 3]: http://blog.csdn.net/jxh_123/article/details/38369373