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

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

在这里插入图片描述

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

链表反转

- 1. 单链表反转实现
- 1. 双链表反转实现
- 1. 相关题型
- - ① 剑指 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 :
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2 ：
输入：head = [1,2]
输出：[2,1]
示例 3 :
输入：head = []
输出：[]

解答：

/**
 * 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 reverseList(ListNode head) {
        ListNode next = null;
        ListNode pre = null;
        while(head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

AC：

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

题目:

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：
输入：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;