【数据结构与算法】单链表反转、双链表反转(含相关题型)

曾经终败给现在 2023-10-14 11:06 66阅读 0赞

![在这里插入图片描述][8d8e0d8a542946af858489a536162608.gif_pic_center]

> 个人简介：Java领域新星创作者；阿里云技术博主、星级博主、专家博主；正在Java学习的路上摸爬滚打，记录学习的过程~  
> 个人主页：[.29.的博客][.29.]  
> 学习社区：[进去逛一逛~][Link 1]

#### 链表反转 ####

*   *  1. 单链表反转 实现
     *  2. 双链表反转 实现
     *  3. 相关题型
     *   *  ① 剑指 Offer II 024. 反转链表 - 力扣（LeetCode）
         *  ② 92. 反转链表 II - 力扣（LeetCode）

### 1. 单链表反转 实现 ###

public class testLinkedList{
        
        
        //单链表 节点(存储int型数据)
        public static class Node{
        
            public int value;
            public Node next;
            public Node(int data){
        
                this.value = data;
            }
        }
        
        //实现单链表反转
        public static Node reverse(Node head){
        
            private Node pre = null;
            private Node next = null;
            while(head != null){
        
                next = head.next;
                head.next = pre;
                pre = head;
                head = next;
            }
            return pre;
        }
        
    }

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

### 2. 双链表反转 实现 ###

public class testDoubleLinkedList{
        
        
        //双链表 节点（存储int型数据）
        public static class DoubleNode{
        
            public int value;
            public DoubleNode last;
            public DoubleNode next;
            public DoubleNode(int data){
        
                this.value = data;
            }
        }
        
        //双链表反转 实现
        public static DoubleNode reverse(DoubleNode head){
        
            public DoubleNode next = null;
            public DoubleNode pre = null;
            while(head != null){
        
                next = head.next;
                head.next = pre;
                head.last = next;
                pre = head;
                head = next;
            }
            return pre;
        }
        
    }

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

### 3. 相关题型 ###

#### ① 剑指 Offer II 024. 反转链表 - 力扣（LeetCode） ####

`题目`：

> 给定单链表的头节点 `head` ，请反转链表，并返回反转后的链表的头节点。
> 
> **示例 1 :**
> 
> ![img][]
> 
>     输入：head = [1,2,3,4,5]
>     输出：[5,4,3,2,1]
> 
> **示例 2 ：**
> 
> ![img][img 1]
> 
>     输入：head = [1,2]
>     输出：[2,1]
> 
> **示例 3 :**
> 
>     输入：head = []
>     输出：[]

`解答`：

`AC`：

> ![在这里插入图片描述][839d8b3636a44da7b71c6ffd307bb430.png_pic_center]

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

#### ② 92. 反转链表 II - 力扣（LeetCode） ####

`题目`:

> 给你单链表的头指针 `head` 和两个整数 `left` 和 `right` ，其中 `left <= right` 。请你反转从位置 `left` 到位置 `right` 的链表节点，返回 **反转后的链表** 。
> 
> **示例 1：**
> 
> ![img][img 2]
> 
>     输入：head = [1,2,3,4,5], left = 2, right = 4
>     输出：[1,4,3,2,5]
> 
> **示例 2：**
> 
>     输入：head = [5], left = 1, right = 1
>     输出：[5]
> 
> **提示 :**
> 
>  *  链表中节点数目为 `n`
>  *  `1 <= n <= 500`
>  *  `-500 <= Node.val <= 500`
>  *  `1 <= left <= right <= n`

`解答`：

*  先遍历，获取到left位置节点与right位置节点
 *  遍历过程中，还需获取left位置前一个节点和right位置后一个节点
 *  之后，将left到right范围内的链表反转
 *  最后维护好反转后链表的头部与尾部指针，并返回头节点即可。

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public ListNode reverseBetween(ListNode head, int left, int right) {
        
            //left 与 right 在同一个位置，无须交换。
            if(left == right) return head;
    
            ListNode next = null;       //当前节点的后一个节点
            ListNode pre = null;        //当前节点的前一个节点
            ListNode leftPre = null;    //left位置节点的前一个节点
            ListNode rightNext = null;  //right位置节点的后一个节点
            ListNode Left = null;       //left位置节点
            ListNode Right = null;      //right位置节点
            ListNode curr = head;       //当前节点指向head节点
            boolean flag = false;       //记录left位置是否为head节点
    
            if(left == 1){
                      //left在第一个位置，说明left位置是head节点
                flag = true;
                Left = curr;
            }
    
            for(int i = 1;i <= right;++i){
        
                if((i + 1) == left){
        
                    leftPre = curr;
                    Left = curr.next;
                }
    
                if(i == right){
        
                    Right = curr;
                    rightNext = curr.next;
                }
                curr = curr.next;
            }
    
            //将left到right位置的链表反转
            curr = Left;
            while(curr != rightNext){
        
                next = curr.next;
                curr.next = pre;
                pre = curr;
                curr = next;
            }
    
            //反转后，left的下一个指向原本right的下一个
            Left.next = rightNext;
            if(flag){
            //若在一开始left就是head
                return Right;  //反转完原本right位置的节点就是头节点
            }
    
            //若在一开始left在head后面，还需要将原本left前一个作为原本right前一个
            leftPre.next = Right;
            return head;
            
        }
    }

`AC`:

> ![在这里插入图片描述][5fdd458715f9491ca6eb1cd5a24866f8.png_pic_center]

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

[![在这里插入图片描述][20a7f1b58dfb4660b75d7f021c157d57.png_pic_center]][20a7f1b58dfb4660b75d7f021c157d57.png_pic_center 1]

[8d8e0d8a542946af858489a536162608.gif_pic_center]: https://img-blog.csdnimg.cn/8d8e0d8a542946af858489a536162608.gif#pic_center
[.29.]: https://blog.csdn.net/ebb29bbe?spm=1018.2226.3001.5343
[Link 1]: https://bbs.csdn.net/forums/185241f773fb401b8ca7994dc3d02333?joinKey=cyru4ex9o7wq-mz6v1koj5x-1-add3ae8dc3827dbbd4360c79af92bbbe
[img]: https://img-blog.csdnimg.cn/img_convert/e45326ba51abea7d72f8eaba9de1f055.jpeg
[img 1]: https://img-blog.csdnimg.cn/img_convert/ce00a3f57c8035708305b15a6c87acbe.jpeg
[839d8b3636a44da7b71c6ffd307bb430.png_pic_center]: https://img-blog.csdnimg.cn/839d8b3636a44da7b71c6ffd307bb430.png#pic_center
[img 2]: https://img-blog.csdnimg.cn/img_convert/5144ee2a95f73e3bcdb45ba63cfc601f.jpeg
[5fdd458715f9491ca6eb1cd5a24866f8.png_pic_center]: https://img-blog.csdnimg.cn/5fdd458715f9491ca6eb1cd5a24866f8.png#pic_center
[20a7f1b58dfb4660b75d7f021c157d57.png_pic_center]: https://img-blog.csdnimg.cn/20a7f1b58dfb4660b75d7f021c157d57.png#pic_center
[20a7f1b58dfb4660b75d7f021c157d57.png_pic_center 1]: https://blog.csdn.net/ebb29bbe?type=blog