剑指offer 面试题24：反转链表

秒速五厘米 2023-02-17 11:15 21阅读 0赞

题目：

> 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。  
> 示例:  
> 输入: 1->2->3->4->5->NULL  
> 输出: 5->4->3->2->1->NULL  
>   
> 限制：  
> 0 <= 节点个数 <= 5000

### 一、迭代 ###

1.  选值，next之后插到前面。

public class ListNode{
        
        int val;
        ListNode next;
        ListNode(int x){
        
            val=x;//构造方法
        }
    }
    
    class Solution {
        
        public ListNode reverseList(ListNode head) {
        
            if(head==null){
        
                return null;
            }
            ListNode ans=new ListNode(head.val);
            head=head.next;
            while(head!=null){
        
                ListNode node=new ListNode(head.val);
                node.next=ans;
                ans=node;
                head=head.next;
            }
            return ans;
        }
    }

1.  改箭头，将每个箭头逆序

输入: 1->2->3->4->5->NULL
    输出: 5->4->3->2->1->NULL
    
    相当于
    
    输入:       1->2->3->4->5->NULL
    输出: NULL<-1<-2<-3<-4<-5

意思也就是说，我们除了一个一个值都取出来之外，还可以直接在链表上进行箭头方向的修改，将它们指向反方向。

我们需要三个节点，一个pre，一个cur，一个nex，分别代表前一个，现在的，和后一个。

*  cur指向 pre 之后，pre 换成 cur，那么在 cur 取了 next 之后就会跑到前面，因此需要在改变方向之前先把 nex 取到正确位置；

nex=cur.next;
                cur.next=pre;

*  在这一次方向翻转之后要更新位置，pre要改到当前的 cur；

pre=cur;

*  然后cur要更新到 nex ,(使用nex 节点是必要的，如果采用 cur 直接指向下一个，此时箭头已经反了，就会取到前面)；

cur=nex;

完整代码如下：

/**
    * Definition for singly-linked list.
    * public class ListNode {
    *     int val;
    *     ListNode next;
    *     ListNode(int x) { val = x; }
    * }
    */
    class Solution {
        
        public ListNode reverseList(ListNode head) {
        
            if(head==null){
        
                return null;
            }
            ListNode pre=null;
            ListNode cur=head;
            ListNode nex=null;
            while(cur!=null){
        
                nex=cur.next;
                cur.next=pre;
                pre=cur;
                cur=nex;//最终跳出cur会为空，因此结果return pre
            }
            return pre;
        }
    }

### 二、递归 ###

类似与上面翻转箭头方向的方法。

递归的向下翻转箭头，直到找到最后一个节点，然后开始翻转，但是要保证 return 回来的是最后一个节点。

/**
    * Definition for singly-linked list.
    * public class ListNode {
    *     int val;
    *     ListNode next;
    *     ListNode(int x) { val = x; }
    * }
    */
    class Solution {
        
        public ListNode reverseList(ListNode head) {
        
            if(head==null||head.next==null){
        
                return head;
            }
            
            ListNode cur=reverseList(head.next);
    
            head.next.next=head;
            head.next=null;
            return cur;
        }
    }

再来看这个代码：

if(head==null||head.next==null){
        
                return head;
    }

这个判断的第一个条件是判断初始的链表是否为空，第二个条件才是真正递归的判断条件。

ListNode cur=reverseList(head.next);

紧接上一步直接就递归调用了，可以看出这个递归的目的仅仅是找到 **倒数第二个节点**，而已。  
因为比如 1->2->3->4->5->NULL，递归进行到 4.next 传入括号内，也就是 5 作为下一轮的 head，发现 5.next 为空，返回了 5，那么 cur 就是 5.

head.next.next=head;
            head.next=null;
            return cur;

当从上一步返回后，进行了当前的 head 的操作，**此时的 head 是 4** ，然后让 5 指向了 4 ，完成了最后一个箭头的逆向；

然后将倒数第二个节点的 next 置空，防止环路产生；

然后 **return cur**，也就是把最后一个节点带回去了。

注意，这一轮开始**往前的每一轮**，递归的返回值都变成了 cur =5 ，也就是最后一个节点，因为上层的 if 条件都不满足，那么在最底层返回一个节点之后，上层的每一层都进行一个箭头的逆序（箭头逆序操作里面和 cur 无关），然后把 cur 返回。

最后就达到了，逆序所有箭头，然后返回了最后一个节点的效果。