リバースリンクリスト

問題声明
シングルリンクスリストの先頭と左と右の2つの整数を指定します.
リストのノードを位置から右へ逆順に反転し、反転したリストを返します.
からの問題文 https://leetcode.com/problems/reverse-linked-list-ii
例1 :

Input: head = [1, 2, 3, 4, 5], left = 2, right = 4
Output: [1, 4, 3, 2, 5]

例2 :

Input: head = [5], left = 1, right = 1
Output: [5]

制約

- The number of nodes in the list is n.
- 1 <= n <= 500
- -500 <= Node.val <= 500
- 1 <= left <= right <= n

解説

反復解法
問題はリンクリストを逆にするのと似ていますが、リスト全体ではなく、我々は逆にする必要があります
サブセットのみです.
オリジナルリスト1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7のサブリスト3 -> 4 -> 5を考慮しましょう
どちらが逆転したいか.サブリストは3＜−4＜−5として反転する必要がある.
現在のノードを4と前のノードを3にします.
設定によって前の次のポインタを簡単に逆にすることができます

current->next = previous

しかし、この場合、ノード5には行けません.したがって、もう一つのポインタが必要です
リンク反転プロセスを継続するのを助けるイテレータと呼びましょう.
そこで以下のようにします.

iterator = current->next
current->next = prev
prev = current
current = iterator

我々は右のノードに到達するまで、上記の手順を続行します.
アルゴリズムをチェックしましょう.

- return NUll if head == NULL

- return head if left == right

- set current = head, prev = NULL

- loop while left > 1
  - set prev = current
  - update current = current->next
  - decrement left--
  - decrement right--

- set tailPrev = prev, tail = current, iterator = NULL

- loop while right > 0
  - iterator = current->next
  - current->next = prev
  - prev = current
  - current = iterator
  - decrement right--

- if tailPrev != NULL
  - set tailPrev->next = prev
- else
  - head = prev

- set tail->next = current

- return head

のC++、golang、およびJavaScriptのソリューションをチェックしましょう.

C++ソリューション

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if(head == NULL) {
            return NULL;
        }

        if(left == right) {
            return head;
        }

        ListNode *current = head, *prev = NULL;

        while(left > 1) {
            prev = current;
            current = current->next;
            left--;
            right--;
        }

        ListNode *tailPrev = prev, *tail = current, *iterator = NULL;

        while(right > 0) {
            iterator = current->next;
            current->next = prev;
            prev = current;
            current = iterator;
            right--;
        }

        if(tailPrev != NULL) {
            tailPrev->next = prev;
        } else {
            head = prev;
        }

        tail->next = current;

        return head;
    }
};

ゴランソリューション

func reverseBetween(head *ListNode, left int, right int) *ListNode {
    if head == nil {
        return nil
    }

    if left == right {
        return head
    }

    current := head
    var prev *ListNode

    for left > 1 {
        prev = current
        current = current.Next
        left--
        right--
    }

    tailPrev, tail := prev, current
    var iterator *ListNode

    for right > 0 {
        iterator = current.Next
        current.Next = prev
        prev = current
        current = iterator
        right--
    }

    if tailPrev != nil {
        tailPrev.Next = prev
    } else {
        head = prev
    }

    tail.Next = current

    return head;
}

ジャバスクリプト

var reverseBetween = function(head, left, right) {
    if(head == null) {
        return null;
    }

    if(left == right) {
        return head;
    }

    let current = head, prev = null;

    while(left > 1) {
        prev = current;
        current = current.next;
        left--;
        right--;
    }

    let tailPrev = prev, tail = current, iterator = null;

    while(right > 0) {
        iterator = current.next;
        current.next = prev;
        prev = current;
        current = iterator;
        right--;
    }

    if(tailPrev != null) {
        tailPrev.next = prev;
    } else {
        head = prev;
    }

    tail.next = current;

    return head;
};

解決策がどのように動くかを見るために、我々のアルゴリズムを実行しましょう.

Input: head = [1, 2, 3, 4, 5], left = 2, right = 4

    head - [1, 2, 3, 4, 5]

Step 1: head == NULL
        false

Step 2: left == right
        2 == 4
        false

Step 3: current = head, prev = null
             current
               |
       head - [1, 2, 3, 4, 5]

Step 3: loop while left > 1
        2 > 1
        true

        prev = current
        current = current->next

                current
                   |
        prev - [1, 2, 3, 4, 5]

        left--
        left = 1

        right --
        right = 3

Step 4: loop while left > 1
        1 > 1
        false

Step 5: tailPrev = prev
                 = 1

        tail = current
             = 2

        iterator = NULL

Step 6: loop while right > 0
        3 > 0
        true

        iterator = current->next
                 = 3

                   iterator
                      |
        prev - [1, 2, 3, 4, 5]

        current->next = prev
        2->next = 1

        prev = current
        prev = 2

        current = iterator
                = 3

        right--
        right = 2

           prev  --    --- iterator
                   |  |
               [1, 2, 3, 4, 5]
                      |
                   current

Step 7: loop while right > 0
        2 > 0
        true

        iterator = current->next
                 = 4

                iterator
                     |
           [1, 2, 3, 4, 5]

        current->next = prev
        3->next = 2

        prev = current
        prev = 3

        current = iterator
                = 4

        right--
        right = 1

               prev  --   --- iterator
                      |  |
               [1, 2, 3, 4, 5]
                         |
                      current

Step 8: loop while right > 0
        1 > 0
        true

        iterator = current->next
                 = 5

                    iterator
                        |
           [1, 2, 3, 4, 5]

        current->next = prev
        4->next = 3

        prev = current
        prev = 4

        current = iterator
                = 5

        right--
        right = 0

                  prev  --  --- iterator
                         |  |
               [1, 2, 3, 4, 5]
                            |
                         current

Step 9: loop while right > 0
        0 > 0
        false

Step 10: tailPrev != NULL
           1 != NULL
           true

           tailPrev->next = prev
           1->next = 4

Step 11: tail->next = current
         2->next = 5

Step 12: return head

So we return the answer as [1, 4, 3, 2, 5].