https://leetcode.com/problems/reverse-linked-list-ii/

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

Solution:

This problem is a “harder” versio of the 206. Reverse Linked List
I followed the idea of 206. Reverse Linked List by first find the
head of the linked list that we need to reverse, then the tail, which is null for the previous qustion. Then start with head,
reverse the linkedlist until we reach the tail node:

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode start = head, pre = null, end = head;
        for (int i = 0; i < n; i++) {
            if (i < m - 1) {
                pre = start;
                start = start.next;
            }
            end = end.next;
        }
        ListNode newHead = null, current = start, next = null;
        while (current != end) {
            next = current.next;
            current.next = newHead;
            newHead = current;
            current = next;
        }
        if (pre != null) {
            pre.next = newHead;
        } else {
            head = newHead;
        }
        start.next = end;
        return head;
    }
}