《算法通关村第二关——终于学会链表反转了》

《算法通关村第二关——终于学会链表反转了》

今天学习链表反转

为什么反转这么重要呢？因为反转链表涉及结点的增加、删除等多种操作，能非常有效考察思维能力和代码驾驭能力。另外很多题目也都要用它来做基础， 例如指定区间反转、链表K个一组翻转。还有一些在内部的某个过程用到了反转，例如两个链表生成相加链表。

下面是实现链表反转的三个方法

有虚拟节点实现链表反转

存在一个虚拟节点我们只需要把原链表的元素一个一个插在虚拟节点的后面就好了。不过需要注意的是在操作的时候要看各个节点的next节点如何处理，一但处理不当就会把链表弄丢。

接下来直接看代码

/**
     * 通过虚拟节点，反转链表
     * @param head 要反转的链表
     * @return 返回反转后的链表的头节点
     */
    public static LinkedNode DummyNodeReverse(LinkedNode head){
        LinkedNode dummyNode = new LinkedNode(-1);
        while(head != null){
            LinkedNode originNext = head.getNext();
            head.setNext(dummyNode.getNext());
            dummyNode.setNext(head);
            head = originNext;
        }
        return dummyNode.getNext();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

无虚拟节点实现链表反转

无虚拟节点的话就需要频繁操作首节点而且，思想是差不多的。

上代码

    /**
     * 没有虚拟节点的链表反转
     * @param head
     * @return
     */

    public static LinkedNode NormalReverse(LinkedNode head){
        LinkedNode temp = null;
        while(head != null){
            LinkedNode originNext = head.getNext();
            head.setNext(temp);
            temp = head;
            head = originNext;
        }
        return temp;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

递归实现链表反转

递归实现链表反转还是有点难理解的，具体如何理解，咱们画图来。

首先有一个链表

我们利用递归对其进行反转，具体代码如下

/**
 * 链表反转的递归形式
 * @param head
 * @return
 */
public static LinkedNode RecurrenceReverse(LinkedNode head){
    if(head == null || head.getNext() ==null){
        return head;
    }
    LinkedNode newHead = RecurrenceReverse(head.getNext());
    head.getNext().setNext(head);
    head.setNext(null);
    return newHead;
}
// 原始
public ListNode reverseList(ListNode head) {  
    if (head == null || head.next == null) {   
        return head;  
    }  
    ListNode newHead = reverseList(head.next);  
    head.next.next = head;  head.next = null;  
    return newHead; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

接下来我们用图进行理解

就上面的 链表传入函数而言，都是在if判断以后就再次进入函数了，何时停止呢，如图。

当在这里递归就返回了后，来到的是head的值是8的时候，newHead指向10，进行一系列的操作如图。

然后在进行返回

再来一张图理解：

到这里应该就理解的差不多了，这个的思想呢就是：当到倒数第一个节点的时候就把倒数第二节点接到倒数第一个节点后面，然后把倒数第二个节点的next赋值为空，后面就是一样的步骤了。其实每次都是在往newHead后面加节点。

近期在自学 Java 做项目，加入了一个编程学习圈子，里面有编程学习路线和原创的项目教程，感觉非常不错。还可以 1 对 1 和大厂嘉宾交流答疑，也希望能对大家有帮助，扫 ⬇️ 二维码即可加入。

也可以点击链接：我正在「编程导航」和朋友们讨论有趣的话题，你⼀起来吧？