首页 > 代码库 > LeetCode: Reverse Linked List II [092]

LeetCode: Reverse Linked List II [092]

2024-07-06 18:44:01   221人阅读

【题目】

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.



【题意】

    给定一个链表，要求反转从第m个节点到第n个节点的子链表，要求一次完成扫描完成，且不能用额外的空间
    m,n满足 1<=m<=n<=链表长度。


【思路】

    先确定要反转的子链表的首尾节点，把子链表拎出来单独做反转。待反转完成之后链回到原来的链表中。


【代码】

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverse(ListNode*head){
        if(head==NULL || head->next==NULL)return head;
        ListNode*prev=NULL;
        ListNode*cur=head;
        ListNode*next=NULL;
        while(cur){
            next=cur->next;
            cur->next=prev;
            prev=cur;
            cur=next;
        }
        return prev;
    }

    ListNode *reverseBetween(ListNode *head, int m, int n) {
        if(head==NULL)return head;
        if(head->next==NULL)return head;
        if(m==n)return head;
        
        int sublinkLen = n-m+1;
        ListNode* prev=NULL;    //指向subhead的前一个节点
        ListNode* subhead=head;
        ListNode* subtail=head;
        ListNode* next=NULL;    //指向subtail的后一个节点
        //subtail先向前移sublinkLen-1了节点
        int count=0;
        while(count<sublinkLen-1){
            subtail=subtail->next;
            count++;
        }
        //此时subhead和subtail正好限定了一个长度为sublinkLen的窗口
        //平移窗口，使得subhead指向第m个节点，subtail指向第n个节点
        count=1;
        while(count<m){
            prev=subhead;
            subhead=subhead->next;
            subtail=subtail->next;
            count++;
        }
        next=subtail->next;
        subtail->next=NULL;
        subtail=subhead;    //反转之后的尾节点
        subhead=reverse(subhead);   //反转链表
        if(prev)prev->next=subhead; //链接会原链表
        else head=subhead;
        subtail->next=next;
        
        return head;
    }
};


联系
我们