LeetCode //C - 92. Reverse Linked List II-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode //C - 92. Reverse Linked List II。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

92. Reverse Linked List II

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:

LeetCode //C - 92. Reverse Linked List II,LeetCode,leetcode,c语言,算法

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

From: LeetCode
Link: 92. Reverse Linked List II

Solution:

Ideas：

1. Handle Edge Cases:

If the head node is NULL or left is equal to right (meaning there’s no need to reverse anything), we immediately return the head.

2. Initialize Dummy Node:

We initialize a dummy node and set its next to head. This is a common trick to simplify code that changes the head node.

3. Move to left-th Node:

We move the prev pointer to the node immediately before the left-th node. The for-loop helps us move it.

4. Initialize cur and next Pointers:

cur is initialized to the left-th node (the node immediately after prev).
next is initialized to NULL.

5. Reverse Segment:

We reverse the segment of the linked list between the left-th and right-th nodes. We do this by iteratively moving nodes from the position immediately after cur to the position immediately after prev.

6. Return New Head:

Finally, we return the new head of the linked list, which is the node immediately after dummy.

By following these steps, we can reverse the segment of the linked list between the left-th and right-th nodes while keeping the rest of the list intact.文章来源地址https://www.toymoban.com/news/detail-679594.html

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseBetween(struct ListNode* head, int left, int right) {
    if (head == NULL || left == right) {
        return head;
    }
    
    struct ListNode *dummy = (struct ListNode*) malloc(sizeof(struct ListNode));
    dummy->val = 0;
    dummy->next = head;
    
    struct ListNode *prev = dummy;
    
    // Move prev pointer to the node before the left-th node
    for (int i = 0; i < left - 1; ++i) {
        prev = prev->next;
    }
    
    struct ListNode *cur = prev->next;
    struct ListNode *next = NULL;
    
    // Reverse the nodes between left and right
    for (int i = 0; i < right - left; ++i) {
        next = cur->next;
        cur->next = next->next;
        next->next = prev->next;
        prev->next = next;
    }
    
    return dummy->next;
}