leetCode-92:Reverse Linked List II

问题描述

给定一个链表和两个数字 left、right，其中1 <= left <= right <= 链表节点数，要求将 [left, right] 区间内的节点进行翻转。题目链接：**点我**

样例输入输出

输入：head = [1,3,5,7,9], left = 2, right = 4

输出：[1,7,5,3,9]

输入：head = [5], left = 1, right = 1

输出：[5]

问题解法

先遍历节点找到开始的地方，然后运用 LeetCode-206 翻转链表的解法对区间内的节点进行翻转。代码如下

/**
 * 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)
    {
        int count = 2;
        ListNode prev = head;
        if (left == 1)
        {
            prev = new ListNode(-1000, head);
            count = 1;
        }
        ListNode p = prev.next;
        while (count < left)
        {
            prev = p;
            p = p.next;
            count++;
        }
        
        while (count < right)
        {
            ListNode temp = prev.next;
            prev.next = p.next;
            p.next = p.next.next;
            prev.next.next = temp;
            count++;
        }
        
        if (left == 1)
        {
            return prev.next;
        }
        
        return head;
    }
}