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

2023-10-17 17:50:01 浏览数 (1)

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

链表反转

1. 单链表反转 实现

代码语言：javascript复制
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. 双链表反转 实现

代码语言：javascript复制
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 :

代码语言：javascript复制
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2 ：

代码语言：javascript复制
输入：head = [1,2]
输出：[2,1]

示例 3 :

代码语言：javascript复制
输入：head = []
输出：[]

解答：

代码语言：javascript复制
/**
 * 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：

代码语言：javascript复制
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2：

代码语言：javascript复制
输入：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范围内的链表反转
  • 最后维护好反转后链表的头部与尾部指针，并返回头节点即可。
代码语言：javascript复制
/**
 * 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:

public 链表 数据 数据结构与算法 指针

0 人点赞