92. Reverse Linked List II

难度: Medium

题目描述

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

 

Example 1:

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Example 2:

Input: head = [5], left = 1, right = 1
Output: [5]

 

Constraints:

• The number of nodes in the list is n.
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

 

Follow up: Could you do it in one pass?

解题思路

代码实现

解决方案

java

/**
 * 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) {
        if (left == right) {
            return head;
        }
        //添加虚拟节点
        ListNode newHead = new ListNode();
        newHead.next = head;

        int index = 1;
        ListNode pLeft = newHead;
        //找到左侧pre节点
        while (index < left) {
            if (pLeft == null) {
                return newHead.next;
            }
            pLeft = pLeft.next;
            index++;
        }

        //找到右侧节点
        ListNode pRight = pLeft;
        while (index <= right) {
            if (pRight == null) {
                return newHead.next;
            }
            pRight = pRight.next;
            index++;
        }
        ListNode pRightNext = pRight.next;
        //从left 开始遍历
        ListNode p = pLeft.next;
        ListNode pLeftNext = p;
        pLeft.next = null;

        //遍历需要翻转的每个节点，进行中插
        while (p != null && p != pRightNext) {

            ListNode next = p.next;

            p.next = null;

            ListNode insertNode = p;
            ListNode tempPLeftNext = pLeft.next;
            pLeft.next = insertNode;
            insertNode.next = tempPLeftNext;

            p = next;

        }
        pLeftNext.next = pRightNext;
        return newHead.next;

    }
}