【leetcode每日一题】NO92.Reverse Linked List II

清疚 2022-08-04 04:14 145阅读 0赞

题目：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值，我们先找到要排序链表部分的起始节点和结束节点，然后对这部分进行排序，再把整个链表连接起来就可以了。

代码：

/**
     * 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||head->next==NULL)
                return head;
            ListNode *first=head;
            ListNode *last=head;
            ListNode *nowNode,*preNode,*nextNode,*temp1,*temp2;
            for(int i=0;i<m-2;i++)
                first=first->next;
            for(int i=0;i<n-1;i++)
                last=last->next;
            if(m==1)
            {
                temp1=first;
                nowNode=first;
            }
            else
            {
                temp1=first->next;
                nowNode=first->next;
            }
            temp2=last->next;
            preNode=NULL;
            while(nowNode!=temp2)
            {
                nextNode=nowNode->next;
                nowNode->next=preNode;
                preNode=nowNode;
                nowNode=nextNode;
            }
            first->next=last;
            temp1->next=temp2;
    		if(m==1)
    			head=last;
            return head;
        }
    };