反转链表——你真的懂了吗？

た入场券 2023-08-17 17:30 118阅读 0赞

**目录**

题目描述：反转一个单链表

数据结构：

方法一：栈

方法二：数组

变形记：

测试：

--------------------

### 题目描述：反转一个单链表 ###

> **示例:**
> 
>     输入: 1->2->3->4->5->NULL
>     输出: 5->4->3->2->1->NULL

### 数据结构： ###

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

### 方法一：栈 ###

借助容器栈，实现十分简单，直接看代码：

public ListNode reverseList(ListNode head) {
            if(head == null || head.next == null)
                return head;
            ListNode node = head;
            Stack<ListNode> stack = new Stack<ListNode>();
            while(node.next != null){
                stack.push(node);
                node = node.next;
            }
            ListNode resultNode = node;
            while(!stack.isEmpty()){
                node.next = stack.pop();
                node = node.next;
            }
            node.next = null;
            return resultNode;
        }

对于其他变形，借助容器依旧可以实现，只是判断条件需要调整，不过多叙述。

值得注意的是，栈的基本**应用场景**：

逆序输出、符号平衡、数制转换、行编辑器、中缀转后缀表达式等，具体可参考：[栈的应用场景][Link 1]

### 方法二：数组 ###

借助指针来实现

**思路一：前驱后继**

public static  ListNode reverseList(ListNode head){
            ListNode pre = null;    //前驱节点
            ListNode cur = head;    //当前节点
            ListNode next = null;   //后继节点
            while (cur != null){
                next = cur.next;    //后继节点后移
                cur.next = pre;     //当前节点指向前驱节点
                pre = cur;          //前驱节点后移
                cur = next;         //当前节点后移
            }
            return pre;             //当前节点为空，前驱节点即为反转后的头节点
        }

** 思路二：头插法**

public static  ListNode reverseList1(ListNode head){
            ListNode pre = new ListNode(-1);
            ListNode cur = head;
            ListNode next = null;
            pre.next = head;         //头插法
    
            while (cur.next != null){//截止条件  null（普通单链表）
                next = cur.next;        //断开前记录后继节点
                cur.next = next.next;   //指向后继的后继
                next.next = pre.next;   //插入头结点后边
                pre.next = next;        //头节点指向新插入的节点
            }
            return pre.next;
        }

### 变形记： ###

> **变形一：**1->2->3->4->5->1
> 
> **变形二：**1->2->3->4->5->4

**1.三种情况通吃：**

public static  ListNode reverseList1(ListNode head){//头插法
            ListNode pre = new ListNode(-1);
            ListNode cur = head;
            ListNode next = null;
            pre.next = head;
    
            while (cur.next != null){//截止条件  null（普通单链表）
                next = cur.next;
                if(cur.next == head){//截止条件 head 环形单链表
                    cur.next = null;
                    break;
                }
                if(next.next == pre.next)//截止条件 n3.next = n2 尾巴环形单链表
                {
                    cur.next = null;
                    pre.next = next;
                    break;
                }
                cur.next = next.next;
                next.next = pre.next;
                pre.next = next;
            }
            return pre.next;
        }

**2.各个击破：**

public static  ListNode reverseList2(ListNode head){//变形一
            ListNode cur = head.next;
            ListNode next = cur.next;
            head.next = null;
            ListNode head1 = head;
            while (head != next){        //环形条件终止
                cur.next = head1;
                head1 = cur;
                cur = next;
                next = next.next;
            }
            cur.next = head1;            //指针调整
            return cur;                  //返回当前节点即为最后反转后的头
        }

public static  ListNode reverseList3(ListNode head){//变形二
            ListNode cur = head.next;
            ListNode next = cur.next;
            head.next = null;
            ListNode head1 = head;
            while (cur != next.next){        //尾部环形条件判定
                cur.next = head1;
                head1 = cur;
                cur = next;
                next = next.next;
            }
            cur.next = head1;                //当前节点指针调整完，最后一个节点不用调整直接返回
            return next;                     
        }

### 测试： ###

public static void main(String[] args) {
            ListNode head = new ListNode(1);
            ListNode n1 = new ListNode(2);
            ListNode n2 = new ListNode(3);
            ListNode n3 = new ListNode(4);
    
            head.next = n1;
            n1.next = n2;
            n2.next = n3;
           // n3.next = head;
            //n3.next = n2;
            ListNode result = reverseList3(head);
            while(result != null){
                System.out.println(result.val);
                result = result.next;
            }
        }

**送上手绘： **

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NjA1MzI4_size_16_color_FFFFFF_t_70][]

[Link 1]: https://blog.csdn.net/lcore/article/details/8867636
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4NjA1MzI4_size_16_color_FFFFFF_t_70]: /images/20230808/d30ede5193f349aba0c88245ed36ec8d.png