首页 > 代码库 > Reverse Linked List II

Reverse Linked List II

2024-07-02 13:58:13   225人阅读

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-1，m，n，n+1，只要把这四个点弄明白后，然后改变m到n间的指针方向，就OK了。首先找出m-1的点，然后找出m点，经循环后得到n和n+1的点。

 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        if(head==NULL)
            return NULL;
        ListNode *pPre=NULL;//找出m-1点的位置
        ListNode *pList=head;
        for(int i=1;i<m;i++)
        {
            pPre=pList;
            pList=pList->next;
        }
        ListNode *pLeft=pList; //m点位置
        ListNode *pRight=pList;//找出n点的位置
        ListNode *pTail;//找出n+1点的位置
        for(int i=m;i<=n;i++)
        {
            pTail=pList->next;
            pList->next=pRight;
            pRight=pList;
            pList=pTail;
        }
        if(pPre==NULL)
        {
            head=pRight;
        }
        else
        {
            pPre->next=pRight;
        }
        pLeft->next=pTail;
        return head;
    }
};

 

 

 


联系
我们