牛客每日刷题之链表

作者简介：我是18shou，一名即将秋招的java实习生

个人主页：_18shou

系列专栏：牛客刷题专栏

推荐一款模拟面试、刷题神器 在线刷题面经模拟面试

目录

题目

思路

题解

复杂度

---

题目

 

描述
将一个节点数为size链表m位置到n位置之间的区间反转，要求时间复杂度O(n)，空间复杂度O(1)。例如:
给出的链表为1→2→3→4→5→NULL, m= 2,n = 4,返回1→4→3→2→5→NULL.
数据范围:链表长度0<size ≤1000，0 < mSn ≤ size，链表中每个节点的值满足|oal|< 1000要求:时间复杂度O(n)，空间复杂度O(n)
进阶:时间复杂度O(n)，空间复杂度O(1)
 

思路

• 要反转局部链表，可以将该局部部分当作完整链表进行反转

• 再将已经反转好的局部链表与其他节点建立连接，重构链表

• 建议使用虚拟头节点的技巧，可以避免对头节点复杂的分类考虑，简化操作。

题解

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 ;
        }
    }
}

复杂度

时间复杂度:O(N)其中N是链表总节点数。最坏情况下，需要遍历整个链表
空间复杂度O(1)仅使用到常数个变量
 

 

结语

兄弟们，一起来刷题嘎嘎的写题