【LeetCode】手撕系列—92. 反转链表 II

• 原题链接：92. 反转链表 II

1-思路

• 先定义一个 dummyHead
• 定义三个指针
  • **pre**：定位到需要被翻转的区间的前一个元素，实现头插
  • **cur**：定位到当前需要被翻转的元素
  • **next**：定位到翻转元素的下一个元素
• 根据 left 定位 pre，从而找到 cur
• 再根据 left 和 right 的差值，依此移动 next ； cur 由于头插法的原因，会自己移动

整体思路为：

• pre 定位到头插法的头部
• 每次移动 next 指针，同时 通过 next 和 cur 指针的变换实现头插法

注：本题指针移动的顺序固定

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

• 第一步，cur.next = next.next 是为了将当前节点（cur）指向 next 的下一个节点，这样做是为了在反转链表时，断开cur和next之间的直接连接，以便将next节点移动到前面去。
• 第二步，next.next = pre.next 是将next节点指向pre的下一个节点，因为我们要将next节点移动到pre和pre的下一个节点之间。
• 第三步，pre.next = next 是更新pre的下一个节点为next，这样next就正式地被移动到了它新的位置。

2-题解

⭐反转链表 II——题解思路

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode pre = dummyHead;
        for(int i = 0 ; i <left-1;i++){
            pre = pre.next;
        }
        ListNode cur = pre.next;
        ListNode next = null;
        for(int i = 0 ; i < right-left;i++){
            next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return dummyHead.next;
    }
}

3-ACM模式

import java.util.List;
import java.util.Scanner;

public class reverseBetween {
    public static class ListNode{
        int val;
        ListNode next;
        ListNode(){}
        ListNode(int x){
            val = x;
        }
    }

    public static ListNode reverseBtwn(ListNode head,int left,int right){
        //
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode pre = dummyHead;
        for(int i = 0 ; i <left-1;i++){
            pre = pre.next;
        }
        ListNode cur = pre.next;
        ListNode next = null;
        for(int i = 0 ; i < right-left;i++){
            next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return dummyHead.next;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("输入链表长度");
        int n = sc.nextInt();
        ListNode head=null,tail=null;
        for(int i = 0 ; i < n;i++){
            ListNode newNode = new ListNode(sc.nextInt());
            if(head==null){
                head = newNode;
                tail = newNode;
            }else{
                tail.next = newNode;
                tail = newNode;
            }
        }
        System.out.println("输入你需要翻转的区间left right");
        int left = sc.nextInt();
        int right = sc.nextInt();
        ListNode forRes = reverseBtwn(head,left,right);
        System.out.println("翻转后的结果是");
        while(forRes!=null){
            System.out.print(forRes.val+" ");
            forRes=forRes.next;
        }
    }
}