首页 > 代码库 > Leetcode:Reverse Linked List II 单链表区间范围内逆置

Leetcode:Reverse Linked List II 单链表区间范围内逆置

2024-07-05 09:19:21   215人阅读

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

代码如下：
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        if(head == NULL)
            return NULL;
        ListNode dummy(0);
        dummy.next = head;
        ListNode *pre = &dummy;
        ListNode *p = head;
        int k = 1;
        
        while(k < m)
        {
            pre = p;
            p = p->next;
            k++;
        }
        
        ListNode *tail = NULL;
        ListNode *nxt = NULL;
        ListNode *tmp = p;
        while(k <= n)
        {
            nxt = p->next;
            p->next = tail;
            tail = p;
            p = nxt;
            k++;
        }
        
        pre->next = tail;
        tmp->next = p;
        
        return dummy.next;
    }
};


联系
我们