牛客在线编程101-02链表内指定区间反转

深藏阁楼爱情的钟 2023-10-04 19:32 57阅读 0赞

### 题目 ###

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。  
例如：  
给出的链表为 1\\to 2 \\to 3 \\to 4 \\to 5 \\to NULL1→2→3→4→5→NULL, m=2,n=4m=2,n=4,  
返回 1\\to 4\\to 3\\to 2\\to 5\\to NULL1→4→3→2→5→NULL.

数据范围： 链表长度 0 < size \\le 10000<size≤1000，0 < m \\le n \\le size0<m≤n≤size，链表中每个节点的值满足 |val| \\le 1000∣val∣≤1000  
要求：时间复杂度 O(n)O(n) ，空间复杂度 O(n)O(n)  
进阶：时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)  
示例1  
输入：  
\{1,2,3,4,5\},2,4  
返回值：  
\{1,4,3,2,5\}  
示例2  
输入：  
\{5\},1,1  
返回值：  
\{5\}

### 解析 ###

将链表拆成两部分：记录下几个边界节点，再重新组合

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类
         */
        public ListNode reverseBetween (ListNode head, int m, int n) {
        
            //虚头节点，可以避免出现m=1和m!=1的情况
            ListNode fake  = new ListNode(-1);
            fake.next = head;
    
            ListNode cur = head;//当前节点，来遍历链表
            //记录几个节点，m位置之前的一个节点和m位置的节点
            ListNode mPre = fake;
            ListNode mNode = head;
            int i = 1;
            while (i < m) {
        
                mPre = cur;
                cur = cur.next;
                mNode = cur;
                i++;
            }
    
    		//翻转链表，和第一题的过程一模一样，反转完成后，pre就是n位置上的节点，cur就是n+1位置上的节点
            ListNode pre = null;
            ListNode next = null;
            while (i <= n) {
        
                next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
                i++;
            }
    		
    		//重新组合链表
            mPre.next = pre;
            mNode.next = cur;
    
            return fake.next;
        }
    }