← Static tasks

24. Swap Nodes in Pairs

leetcode medium

#csharp#leetcode#linked-list#medium

Task

Учитывая связанный список, поменяйте местами каждые два соседних узла и верните его голову. Вы должны решить проблему, не изменяя значения в узлах списка (т. е. изменять можно только сами узлы).

C# solution

matched/original
public ListNode SwapPairs(ListNode head)
        {
            if (head == null)
                return head;
            ListNode s = head;
            ListNode h1 = head;
            ListNode h2 = head.next;
            while (h2 != null)
            {
                //SWAP
                var t = h1.val;
                h1.val = h2.val;
                h2.val = t;
                if (h2.next == null || h1.next.next == null)
                    break;
                // move by +2 
                h2 = h2.next.next;
                h1 = h1.next.next;
            }
            return s;
        }

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public ListNode SwapPairs(ListNode head)
        {
            if (head == null)
                return head;
            ListNode s = head;
            ListNode h1 = head;
            ListNode h2 = head.next;
            while (h2 != null)
            {
                //SWAP
                var t = h1.val;
                h1.val = h2.val;
                h2.val = t;
                if (h2.next == null || h1.next.next == null)
                    break;
                // move by +2 
                h2 = h2.next.next;
                h1 = h1.next.next;
            }
            return s;
        }

Java solution

matched/original
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next==null) return head;
        ListNode second = head.next;
        ListNode pr = swapPairs(second.next);
        second.next = head;
        head.next = pr;
        return second;
    }
}

JavaScript solution

matched/original
/
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function (head) {
    if (!head || !head.next) {
        return head;
    }
    const t = swapPairs(head.next.next);
    const p = head.next;
    p.next = head;
    head.next = t;
    return p;
};

Python solution

matched/original
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]: 
        if  not (head and head.next): 
            return head 
        head, head.next, head.next.next = head.next, head, self.swapPairs(head.next.next) 
        return head

Go solution

matched/original
func swapPairs(head *ListNode) *ListNode {
    newHead := &ListNode{
        Next: head,
    }
    prev := newHead
    i := head
    if i == nil {
        return head
    }
    j := head.Next
    for i != nil && j != nil {
        prev.Next = j
        i.Next = j.Next
        j.Next = i
        if i.Next == nil {
            break
        }
        prev, i, j = i, i.Next, i.Next.Next
    }
    return newHead.Next
}

Explanation

Данный код реализует функцию SwapPairs для обмена парами значений в узлах односвязного списка. Вот краткое объяснение кода:

1. Проверка наличия списка: Если голова списка head равна null, то функция возвращает head без изменений.

2. Инициализация переменных: Создаются три указателя на узлы - s (хранит ссылку на начало списка), h1 (указывает на текущий узел) и h2 (указывает на следующий узел после h1).

3. Цикл обмена парами: Пока h2 не станет равным null (то есть список содержит хотя бы два узла), выполняется следующее:

- Значения узлов h1 и h2 меняются местами.

- Выполняется проверка на окончание списка: если

h2.next

равен null или

h1.next.next

равен null (то есть остался только один узел или ни одного), цикл прерывается.

- Указатели h1 и h2 смещаются на два узла вперед, чтобы перейти к следующей паре узлов.

4. Возвращение начальной головы: После обмена всех попарных значений в узлах функция возвращает начальную голову списка s.

Функция SwapPairs попарно обменивает значения узлов в односвязном списке до конца списка, сохраняя ссылку на начало списка.