1
struct ListNode {
2
    int val;
3
    ListNode *next;
4
    ListNode() : val(0), next(nullptr) {}
5
    ListNode(int x) : val(x), next(nullptr) {}
6
    ListNode(int x, ListNode *next) : val(x), next(next) {}
7
};

1
class ListNode {
2
    constructor(val, next) {
3
        this.val = (val === undefined ? 0 : val);
4
        this.next = (next === undefined ? null : next);
5
    }
6
}

1
#include <stddef.h>
2

3
typedef struct ListNode {
4
    int val;
5
    struct ListNode *next;
6
} ListNode;
7

8
/* ============ 1. Reverse the entire linked list ============ */
9

10
/* Iterative */
11
ListNode* reverseList(ListNode* head) {
12
    ListNode* prev = NULL;
13
    ListNode* curr = head;
14
    while (curr) {
15
        ListNode* next = curr->next; /* save the successor first */
16
        curr->next = prev;           /* reverse the current pointer */
17
        prev = curr;                 /* advance prev */
18
        curr = next;                 /* advance curr */
19
    }
20
    return prev;
21
}
22

23
/* Recursive */
24
ListNode* reverseListRecursive(ListNode* head) {
25
    if (head == NULL || head->next == NULL) return head;
26
    ListNode* last = reverseListRecursive(head->next);
27
    head->next->next = head; /* successor points to itself */
28
    head->next = NULL;       /* break the original pointer */
29
    return last;
30
}
31

32
/* ============ 2. Reverse the first N nodes ============ */
33

34
/* Iterative */
35
ListNode* reverseN(ListNode* head, int n) {
36
    ListNode* prev = NULL;
37
    ListNode* curr = head;
38
    for (int i = 0; i < n && curr; i++) {
39
        ListNode* next = curr->next;
40
        curr->next = prev;
41
        prev = curr;
42
        curr = next;
43
    }
44
    head->next = curr; /* attach the original head to the remaining part */
45
    return prev;
46
}
47

48
/* Recursive (using the successor pointer) */
49
static ListNode* successor = NULL;
50

51
ListNode* reverseNRecursive(ListNode* head, int n) {
52
    if (n == 1) {
53
        successor = head->next; /* record the (n+1)-th node */
54
        return head;
55
    }
56
    ListNode* last = reverseNRecursive(head->next, n - 1);
57
    head->next->next = head;
58
    head->next = successor; /* attach the reversed tail to the successor */
59
    return last;
60
}
61

62
/* ============ 3. Reverse part of the linked list (interval [left, right]) ============ */
63

64
/* Iterative (head insertion) */
65
ListNode* reverseBetween(ListNode* head, int left, int right) {
66
    ListNode dummy;
67
    dummy.next = head;
68
    ListNode* pre = &dummy;
69
    for (int i = 1; i < left; i++) pre = pre->next; /* locate the predecessor of left */
70

71
    ListNode* curr = pre->next;
72
    for (int i = 0; i < right - left; i++) {
73
        ListNode* next = curr->next;
74
        curr->next = next->next;
75
        next->next = pre->next;
76
        pre->next = next;
77
    }
78
    return dummy.next;
79
}
80

81
/* Recursive (reduces to reversing the first right nodes) */
82
ListNode* reverseBetweenRecursive(ListNode* head, int left, int right) {
83
    if (left == 1) {
84
        return reverseNRecursive(head, right);
85
    }
86
    head->next = reverseBetweenRecursive(head->next, left - 1, right - 1);
87
    return head;
88
}
89

90
/* ============ 4. Reverse in groups of K ============ */
91

92
/* Iterative */
93
ListNode* reverseKGroup(ListNode* head, int k) {
94
    ListNode dummy;
95
    dummy.next = head;
96
    ListNode* pre = &dummy;
97
    ListNode* end = &dummy;
98

99
    while (end->next) {
100
        for (int i = 0; i < k && end; i++) end = end->next; /* probe ahead */
101
        if (!end) break; /* fewer than k, stop */
102

103
        ListNode* start = pre->next;
104
        ListNode* next = end->next;      /* record the start of the next group */
105
        end->next = NULL;                /* cut off this group */
106
        pre->next = reverseList(start);  /* reverse this group */
107
        start->next = next;              /* reconnect the rest */
108
        pre = start;                     /* pre points to the end of this group */
109
        end = pre;                       /* reset end */
110
    }
111
    return dummy.next;
112
}
113

114
/* Recursive */
115
ListNode* reverseKGroupRecursive(ListNode* head, int k) {
116
    ListNode* end = head;
117
    for (int i = 0; i < k; i++) {
118
        if (!end) return head; /* fewer than k, keep as is */
119
        end = end->next;
120
    }
121

122
    ListNode* newHead = reverseN(head, k);               /* reverse the first k */
123
    head->next = reverseKGroupRecursive(end, k);         /* recursively process the rest */
124
    return newHead;
125
}

1
class ListNode {
2
    constructor(val, next) {
3
        this.val = (val === undefined ? 0 : val);
4
        this.next = (next === undefined ? null : next);
5
    }
6
}
7

8
// successor pointer used by the recursive "reverse first N"
9
let successor = null;
10

11
/* ============ 1. Reverse the entire linked list ============ */
12

13
function reverseList(head) {
14
    let prev = null;
15
    let curr = head;
16
    while (curr) {
17
        const next = curr.next;
18
        curr.next = prev;
19
        prev = curr;
20
        curr = next;
21
    }
22
    return prev;
23
}
24

25
function reverseListRecursive(head) {
26
    if (!head || !head.next) return head;
27
    const last = reverseListRecursive(head.next);
28
    head.next.next = head;
29
    head.next = null;
30
    return last;
31
}
32

33
/* ============ 2. Reverse the first N nodes ============ */
34

35
function reverseN(head, n) {
36
    let prev = null;
37
    let curr = head;
38
    for (let i = 0; i < n && curr; i++) {
39
        const next = curr.next;
40
        curr.next = prev;
41
        prev = curr;
42
        curr = next;
43
    }
44
    head.next = curr;
45
    return prev;
46
}
47

48
function reverseNRecursive(head, n) {
49
    if (n === 1) {
50
        successor = head.next;
51
        return head;
52
    }
53
    const last = reverseNRecursive(head.next, n - 1);
54
    head.next.next = head;
55
    head.next = successor;
56
    return last;
57
}
58

59
/* ============ 3. Reverse part of the linked list ============ */
60

61
function reverseBetween(head, left, right) {
62
    const dummy = new ListNode(0, head);
63
    let pre = dummy;
64
    for (let i = 1; i < left; i++) pre = pre.next;
65

66
    const curr = pre.next;
67
    for (let i = 0; i < right - left; i++) {
68
        const next = curr.next;
69
        curr.next = next.next;
70
        next.next = pre.next;
71
        pre.next = next;
72
    }
73
    return dummy.next;
74
}
75

76
function reverseBetweenRecursive(head, left, right) {
77
    if (left === 1) {
78
        return reverseNRecursive(head, right);
79
    }
80
    head.next = reverseBetweenRecursive(head.next, left - 1, right - 1);
81
    return head;
82
}
83

84
/* ============ 4. Reverse in groups of K ============ */
85

86
function reverseKGroup(head, k) {
87
    const dummy = new ListNode(0, head);
88
    let pre = dummy;
89
    let end = dummy;
90

91
    while (end.next) {
92
        for (let i = 0; i < k && end; i++) end = end.next;
93
        if (!end) break;
94

95
        const start = pre.next;
96
        const next = end.next;
97
        end.next = null;
98
        pre.next = reverseList(start);
99
        start.next = next;
100
        pre = start;
101
        end = pre;
102
    }
103
    return dummy.next;
104
}
105

106
function reverseKGroupRecursive(head, k) {
107
    let end = head;
108
    for (let i = 0; i < k; i++) {
109
        if (!end) return head;
110
        end = end.next;
111
    }
112
    const newHead = reverseN(head, k);
113
    head.next = reverseKGroupRecursive(end, k);
114
    return newHead;
115
}