Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

Условие

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

Example 1: Input: head = [1,2,3,4] Output: [2,1,4,3] Explanation:

Example 2: Input: head = [] Output: []

Example 3: Input: head = [1] Output: [1]

Example 4: Input: head = [1,2,3] Output: [2,1,3]

Ответ

Меняйте ссылки у каждой соседней пары, используя фиктивный узел перед головой. Значения узлов остаются неизменными; непарный последний узел сохраняет место.

function swapPairs(head) {
  const dummy = { next: head };
  let previous = dummy;
  while (previous.next && previous.next.next) {
    const first = previous.next;
    const second = first.next;
    first.next = second.next;
    second.next = first;
    previous.next = second;
    previous = first;
  }
  return dummy.next;
}

Здесь каждый узел имеет поле next, а конец списка равен null. Время O(n), дополнительная память O(1); список меняется на месте, пустой вход и один узел обрабатываются без особых ветвей.