143. Reorder List

LeetCode medium оригинал: C# #csharp #leetcode #linked-list #medium #two-pointers

LeetCode Static

Вам дана голова односвязного списка. Список можно представить в следующем виде:

L0 → L1 → … → Ln - 1 → Ln

Переупорядочите список так, чтобы он принял следующую форму:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

Вы не можете изменять значения в узлах списка. Можно изменять только сами узлы.

Пример:

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

Output: [1,4,2,3]

C# решение

сопоставлено/оригинал

public class Solution {
    public void ReorderList(ListNode head) {
        if (head == null)
            return;
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode prev = null, curr = slow, tmp;
        while (curr != null) {
            tmp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = tmp;
        }
        ListNode first = head, second = prev;
        while (second.next != null) {
            tmp = first.next;
            first.next = second;
            first = tmp;
            tmp = second.next;
            second.next = first;
            second = tmp;
        }
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public void ReorderList(ListNode head) {
        if (head == null)
            return;
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode prev = null, curr = slow, tmp;
        while (curr != null) {
            tmp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = tmp;
        }
        ListNode first = head, second = prev;
        while (second.next != null) {
            tmp = first.next;
            first.next = second;
            first = tmp;
            tmp = second.next;
            second.next = first;
            second = tmp;
        }
    }
}

Java решение

сопоставлено/оригинал

class Solution {
    public void reorderList(ListNode head) {
        if (head == null) return;

        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode prev = null, curr = slow, tmp;
        while (curr != null) {
            tmp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = tmp;
        }

        ListNode first = head, second = prev;
        while (second.next != null) {
            tmp = first.next;
            first.next = second;
            first = tmp;

            tmp = second.next;
            second.next = first;
            second = tmp;
        }
    }
}

JavaScript решение

сопоставлено/оригинал

var reorderList = function (head) {
    if (head === null) return;
    let slow = head;
    let fast = head;
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    let prev = null;
    let curr = slow;
    while (curr !== null) {
        let tmp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = tmp;
    }
    let first = head;
    let second = prev;
    while (second.next !== null) {
        let tmp = first.next;
        first.next = second;
        first = tmp;
        tmp = second.next;
        second.next = first;
        second = tmp;
    }
};

Python решение

сопоставлено/оригинал

class Solution:
    def reorderList(self, head: ListNode) -> None:
        if not head:
            return

        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        prev, curr = None, slow
        while curr:
            curr.next, prev, curr = prev, curr, curr.next

        first, second = head, prev
        while second.next:
            first.next, first = second, first.next
            second.next, second = first, second.next

Go решение

сопоставлено/оригинал

func reorderList(head *ListNode) {
    if head == nil {
        return
    }
    slow := head
    fast := head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    var prev, curr *ListNode = nil, slow
    for curr != nil {
        tmp := curr.Next
        curr.Next = prev
        prev = curr
        curr = tmp
    }
    first := head
    second := prev
    for second.Next != nil {
        tmp := first.Next
        first.Next = second
        first = tmp
        tmp = second.Next
        second.Next = first
        second = tmp
    }
}

Algorithm

1️⃣

Нахождение середины списка и разделение его на две части:

Используйте два указателя, slow и fast, для нахождения середины списка. Указатель slow движется на один узел за шаг, а fast — на два узла. Когда fast достигает конца списка, slow окажется в середине.

Разделите список на две части. Первая часть начинается от головы списка до slow, вторая — с узла после slow до конца списка.

2️⃣

Реверс второй половины списка:

Инициализируйте указатели prev как NULL и curr как slow. Перемещайтесь по второй половине списка и меняйте направление ссылок между узлами для реверсирования списка.

Продолжайте, пока не перестроите весь второй сегмент, теперь последний элемент первой части списка будет указывать на NULL, а prev станет новой головой второй половины списка.

3️⃣

Слияние двух частей списка в заданном порядке:

Начните с головы первой части списка (first) и головы реверсированной второй части (second).

Перекрестно связывайте узлы из первой и второй части, вставляя узлы из второй части между узлами первой части. Передвигайте указатели first и second соответственно после каждой вставки.

Продолжайте этот процесс до тех пор, пока узлы второй части не закончатся.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.