【算法练习】4种反转链表的方法（Java实现）

目录

前言：

题目：

方法一：迭代法

方法二：头插法

方法三：递归法

方法四：栈辅助

       总结：

前言：

        本文阅读基础：有一定的数据结构知识，了解单向链表。

题目：

        单向链表：1,2,3,4,5  反向输出，期待：5,4,3,2,1

        定义一个单向链表：

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
        
        // 此处省略get,set方法
    }

main方法：

public static void main(String[] args) {
        ListNode five = new ListNode(5);
        ListNode four = new ListNode(4);
        four.next = five;
        ListNode three = new ListNode(3);
        three.next = four;
        ListNode two = new ListNode(2);
        two.next = three;
        ListNode one = new ListNode(1);
        one.next = two;
        // 反转
        one = Solution.reverseList(one);
        // 输出
        while (one != null) {
            System.out.println(one.val);
            one = one.next;
        }

    }

方法一：迭代法

思路：从第二个开始，逐个反转

关键：将当前节点的下一个节点记下；将当前节点和已有的head反转，使当前节点做为新的head；

public static class Solution {
    public static ListNode reverseList(ListNode head) {
        if(head == null || head.next() == null){
            return head;
        }
        ListNode cur = head.next();
        head.next = null;
        while(cur != null){
            ListNode next = cur.next();
            cur.next = head;
            head = cur;
            cur = next;
        }
        return head;
    }
}

第一次进入：head =1,cur = 2(2->3->4->5);

第二次进入：head =2(2->1),cur = 3(3->4->5);

第三次进入：head =3(3->2->1),cur = 4(4->5);

第四次进入：head =4(4->3->2->1),cur = 5(5->null);

方法二：头插法

思路：使用一个空节点作为反转后链表的头,每次将原链表的头节点插入到空节点后面,最后返回新链表的头节点。

关键：返回newHead 的next

public static class Solution {
    public static ListNode reverseList(ListNode head) {
        if(head == null || head.next() == null){
            return head;
        }
        
        ListNode newHead = new ListNode(0); // 新的头
        while(head != null){
            ListNode next = head.next();
            head.next = newHead.next();
            newHead.next = head;
            head = next;
        } 
        return newHead.next();
}

第一次进入：newHead = 0,head = 1(1->2->3->4->5);

第二次进入：newHead = 0(0->1),head = 2(2->3->4->5);

第三次进入：newHead = 0(0->2->1),head = 3(3->4->5);

第四次进入：newHead = 0(0->3->2->1),head = 4(4->5);

第五次进入：newHead = 0(0->4->3->2->1),head = 5(5->null);

（也可以在开始将newHead.next()设置为1，能减少一次循环）

方法三：递归法

递归法比较有意思，大家可以结合之前我们聊过的内存分析来理解递归法[Java基础]面向对象-内存解析_小王师傅66的博客-CSDN博客

关键：递归的入口是head.next，不是head，才能递归到最后两个节点

public static class Solution {
    public static ListNode reverseList(ListNode head) {
        if(head == null || head.next() == null){ // 1
            return head;
        }
    
        ListNode newHead = reverseList(head.next); // 1
        head.next.next = head; // 2 反转当前节点和下一个节点 
        head.next = null; // 3
        return newHead; // 4
    }
}

当head = 4时，head.next()=5,执行到reverseList()方法时返回head。

此时：5<-4<-3<-2<-1，newHead = 5, head= 4(4->5)，经过2,3反转得到：5->4 , 3<-2<-1；

(在第3步，我们已经将4.next置为null);

所以过程如下：

1）5 , 4<-3<-2<-1；

2）5->4 , 3<-2<-1；

3）5->4->3, 2<-1；

4)  5->4->3->2, 1;

最后输出newHead = 5(5->4->3->2->1).

方法四：栈辅助

这个方法就比较简单了，用的Java的工具包Stack类。我们知道栈的特点是先进后出，所以思路就是：将所有节点依次入栈,然后出栈的顺序就是反转后的顺序,根据这个顺序重建链表。

public static class Solution {
    public static ListNode reverseList(ListNode head){
        Stack<ListNode> stack = new Stack<>();
        while (head !=null){
            stack.push(head);
            head = head.next;
        }
        if(stack.isEmpty()) return null;
        ListNode newHead = stack.pop();
        head = newHead;
        while(!stack.isEmpty()){
            head.next = stack.pop();
            head = head.next;
        }
        head.next = null;
        return newHead;
    }

}

        方法比较简单，这里我就不列举值的变化了，大家可以自行推导一下。

       总结：

        主要区别在于迭代法和递归法是在原链表上直接反转,无需额外空间;而头插法和栈辅助需要 O(N) 的额外空间。一般迭代法代码最简洁,递归法需要处理终止条件,但思路清晰。         

        当然还有很多反转链表的方法，以上只是列举4种典型的方法。通过这4种方法，我们可以看到，思路不一样，实现方法完全不一样。