当前位置：网站首页>＃yyds干货盘点＃面试必刷TOP101：链表内指定区间反转

＃yyds干货盘点＃面试必刷TOP101：链表内指定区间反转

2022-07-27 15:37:00 【51CTO】

1.简述：

描述

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度，空间复杂度。例如：给出的链表为 , ,返回 .

数据范围：链表长度，，链表中每个节点的值满足

要求：时间复杂度，空间复杂度

进阶：时间复杂度，空间复杂度

示例1

输入：

       
       {1,2,3,4,5},2,4
      
1.

返回值：

       
       {1,4,3,2,5}
      
1.

示例2

输入：

返回值：

2.代码实现：

       
       import java.util.*;
       
/*
       
 * public class ListNode {
       
 *   int val;
       
 *   ListNode next = null;
       
 * }
       
 */
       
public class Solution {
       
    /**
       
     * 
       
     * @param head ListNode类 
       
     * @param m int整型 
       
     * @param n int整型 
       
     * @return ListNode类
       
     */
       
       // 解法一：双指针(两次遍历)
       
       //说明：方便理解，以下注释中将用left，right分别代替m,n节点 
       
    public ListNode reverseBetween (ListNode head, int m, int n) {
       
             //设置虚拟头节点
       
        ListNode dummyNode = new ListNode(-1);
       
        dummyNode.next = head;
       
        ListNode pre = dummyNode;
       
        //1.走left-1步到left的前一个节点
       
        for(int i=0;i<m-1;i++){
       
            pre = pre.next;
       
        }
       
        //2.走roght-left+1步到right节点
       
        ListNode rigthNode = pre;
       
        for(int i=0;i<n-m+1;i++){
       
            rigthNode = rigthNode.next;
       
        }
       
        //3.截取出一个子链表
       
        ListNode leftNode = pre.next;
       
        ListNode cur = rigthNode.next;
       
        //4.切断链接
       
        pre.next=null;
       
        rigthNode.next=null;
       
        //5.反转局部链表
       
        reverseLinkedList(leftNode);
       
        //6.接回原来的链表
       
        pre.next = rigthNode;
       
        leftNode.next = cur;
       
        return dummyNode.next;
       
    }
       
    //反转局部链表
       
    private void reverseLinkedList(ListNode head){
       
        ListNode pre = null;
       
        ListNode cur = head;
       
        while(cur!=null){
       
            //Cur_next 指向cur节点的下一个节点
       
            ListNode Cur_next = cur.next;
       
            cur.next = pre;
       
            pre = cur;
       
            cur = Cur_next ;
       
        }
       
    }
       
}
       
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.