2.1.1 Singly Linked List

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153

/*

Implements common singly linked list operations using raw nodes. Manual linked list implementations
are rarely the best practical choice over arrays, vectors, or `std::list`, but the pointer patterns
are useful for interview-style problems and understanding constant-time splicing.

For production C++, prefer containers such as `std::list`, `std::forward_list`, or `std::vector`
when they fit the problem. Use the raw-node style below when the problem statement already gives
nodes, or when manual pointer manipulation is the point of the exercise.

- `reverse_list(head)` reverses a singly linked list and returns the new head.
- `split_half(head, &second)` cuts a list into two halves, returning the first half and storing the
  second half in `second`.
- `merge_sorted_lists(a, b)` merges two sorted lists using a dummy node and returns the merged head.
- `splice_after(pos, before)` moves the node after `before` so it appears after `pos`.
- `splice_range_after(pos, before_first, last)` moves the half-open range (`before_first`, `last`)
  so it appears after `pos`.

The splicing helpers use the same "after" convention as `std::forward_list::splice_after()`. They
work naturally with a dummy head node, which makes insertions and removals at the beginning of a
list match all other positions. For `splice_range_after()`, `pos` must not lie inside the moved
range. For doubly linked list splicing, use the next section.

For cycle detection, see the variant on iterated functions in chapter 1, which can be easily adapted
for linked lists.

Time Complexity:
- O(n) per call to `reverse_list()` and `split_half()`.
- O(n + m) per call to `merge_sorted_lists()`.
- O(1) per call to `splice_after()`.
- O(k) per call to `splice_range_after()`, where $k$ is the number of moved nodes. The actual
  pointer splicing is O(1), but this compact version walks to the end of the moved range.

Space Complexity:
- O(1) auxiliary for all operations.

*/

struct ListNode {
  int value;
  ListNode *next;

  explicit ListNode(int value = 0) : value(value), next(nullptr) {}
};

ListNode *reverse_list(ListNode *head) {
  ListNode *prev = nullptr;
  while (head != nullptr) {
    ListNode *next = head->next;
    head->next = prev;
    prev = head;
    head = next;
  }
  return prev;
}

ListNode *split_half(ListNode *head, ListNode **second) {
  if (head == nullptr || head->next == nullptr) {
    *second = nullptr;
    return head;
  }
  ListNode *slow = head, *fast = head->next;
  while (fast != nullptr && fast->next != nullptr) {
    slow = slow->next;
    fast = fast->next->next;
  }
  *second = slow->next;
  slow->next = nullptr;
  return head;
}

ListNode *merge_sorted_lists(ListNode *a, ListNode *b) {
  ListNode dummy;
  ListNode *tail = &dummy;
  while (a != nullptr && b != nullptr) {
    if (b->value < a->value) {
      tail->next = b;
      b = b->next;
    } else {
      tail->next = a;
      a = a->next;
    }
    tail = tail->next;
  }
  tail->next = a != nullptr ? a : b;
  return dummy.next;
}

void splice_after(ListNode *pos, ListNode *before) {
  ListNode *node = before->next;
  if (node == nullptr || pos == before || pos == node) {
    return;
  }
  before->next = node->next;
  node->next = pos->next;
  pos->next = node;
}

void splice_range_after(ListNode *pos, ListNode *before_first, ListNode *last) {
  ListNode *first = before_first->next;
  if (first == last) {
    return;
  }
  ListNode *tail = first;
  while (tail->next != last) {
    tail = tail->next;
  }
  before_first->next = last;
  tail->next = pos->next;
  pos->next = first;
}

/*** Example Usage ***/

#include <cassert>
#include <vector>
using namespace std;

vector<int> values(ListNode *head) {
  vector<int> res;
  for (; head != nullptr; head = head->next) {
    res.push_back(head->value);
  }
  return res;
}

int main() {
  vector<ListNode> a{ListNode(1), ListNode(3), ListNode(5)};
  vector<ListNode> b{ListNode(2), ListNode(4), ListNode(6)};
  for (int i = 0; i + 1 < static_cast<int>(a.size()); i++) {
    a[i].next = &a[i + 1];
    b[i].next = &b[i + 1];
  }
  ListNode *merged = merge_sorted_lists(&a[0], &b[0]);
  assert((values(merged) == vector<int>{1, 2, 3, 4, 5, 6}));

  ListNode *second = nullptr;
  ListNode *first = split_half(merged, &second);
  assert((values(first) == vector<int>{1, 2, 3}));
  assert((values(second) == vector<int>{4, 5, 6}));
  assert((values(reverse_list(first)) == vector<int>{3, 2, 1}));

  ListNode dummy(0), w(1), x(2), y(3), z(4);
  dummy.next = &w;
  w.next = &x;
  x.next = &y;
  y.next = &z;
  splice_after(&dummy, &y);  // Move 4 to the front: 4, 1, 2, 3.
  assert((values(dummy.next) == vector<int>{4, 1, 2, 3}));
  splice_range_after(&z, &w, nullptr);  // Move 2, 3 after 4: 4, 2, 3, 1.
  assert((values(dummy.next) == vector<int>{4, 2, 3, 1}));
  return 0;
}