leetcode92: Reverse Linked List II

[carloscn]

Description

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:

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

Example 2:

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

Constraints:

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

[carloscn]

Analysis

局部的翻转链表。分为两个关键步骤比较难：

• 互换L和R

  • PL->next = R
  • RP->next = L
  • t = R->next
  • R = L->next
  • L->next = t

• 两个链表指针需要向内移动 （由于这个不是双向链表，因此R指针向前移动为难点，需要一个while循环重头遍历找到）

  • 移动L节点： PL= L, L = L->next
  • 移动R节点: R = RP, while(PR->next != R) { R = R->next }

[carloscn]

code

int32_t reverse_between(LINKLIST_T *in_list, size_t left, size_t right)
{
    int32_t ret = 0;

    UTILS_CHECK_PTR(in_list);

    if (left > right || left == 0) {
        ret = -1;
        goto finish;
    }

    if (left == right) {
        goto finish;
    }

    size_t ln = left - 1;
    size_t rn = right - 1;
    LINKLIST_T *L = in_list, *R = in_list, *PR = NULL;

    // Find left header
    while (ln --) {
        L = L->next;
    }

    // Find right header
    while (rn --) {
        PR = R;
        R = R->next;
    }

    rn = right - left - 1;

    while (rn --) {
        ret = linklist_swap_value(L, R);
        UTILS_CHECK_RET(ret);

        L = L->next;
        R = PR;
        PR = in_list;
        while (PR->next != R) {
            PR = PR->next;
        }
    }

finish:
    return ret;
}

[carloscn]

code

https://review.gerrithub.io/c/carloscn/structstudy/+/556957 https://github.com/carloscn/structstudy/commit/6010dee400553337700992295a295dda65858aa3