面试题24 反转链表

落日映苍穹つ 2023-02-09 14:19 28阅读 0赞

# 题目来源 #

[面试题24 反转链表][24]  
[206. 反转链表][206.]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

# 题目解析 #

## 双指针 ##

*  定义两个指针： prepre 和 curcur ；prepre 在前 curcur 在后。
 *  每次让 prepre 的 nextnext 指向 curcur ，实现一次局部反转
 *  局部反转完成之后， prepre 和 curcur 同时往前移动一个位置
 *  循环上述过程，直至 prepre 到达链表尾部

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

![在这里插入图片描述][20200519132139283.gif]

![在这里插入图片描述][20200519134301217.png]

## 递归 ##

*  使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作 ret .
 *  此后，每次函数在返回的过程中，让当前结点的下一个结点的 next 指针指向当前节点。
 *  同时让当前结点的 next指针指向 NULL ，从而实现从链表尾部开始的局部反转
 *  当递归函数全部出栈后，链表反转完成。

![在这里插入图片描述][20200519132743404.gif]

class Solution {
        
        public ListNode reverseList(ListNode head) {
        
            if (head == null || head.next == null){
        
                return head;
            }
    
            ListNode ret = reverseList(head.next);
            head.next.next = head;  // 我【head】的下一个节点【next】指向【next】指向我自己【head】
            head.next = null; // 我自己【head】指向【next】空【null】
    
            return ret;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][20200519134258956.png]

## 头插法 ##

遍历已有链表，对每个元素实行头插法插入到一个新的链表当中从而完成逆序。

class Solution {
        
        public ListNode reverseList(ListNode head) {
        
            if (head == null ){
        
                return head;
            }
    
            ListNode dummy = null;
            while(head != null){
        
                ListNode node = new ListNode(head.val);
                node.next = dummy;
                dummy = node;
                head = head.next;
            }
            
            return dummy;
        }
    }

![在这里插入图片描述][20200519134557677.png]

[24]: https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
[206.]: https://leetcode-cn.com/problems/reverse-linked-list/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200519135648936.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[20200519132139283.gif]: https://img-blog.csdnimg.cn/20200519132139283.gif
[20200519134301217.png]: https://img-blog.csdnimg.cn/20200519134301217.png
[20200519132743404.gif]: https://img-blog.csdnimg.cn/20200519132743404.gif
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200624155623543.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[20200519134258956.png]: https://img-blog.csdnimg.cn/20200519134258956.png
[20200519134557677.png]: https://img-blog.csdnimg.cn/20200519134557677.png