【LeetCode】92. 反转链表 II

素颜马尾好姑娘i 2022-05-11 11:20 147阅读 0赞

**题目链接**：[https://leetcode-cn.com/problems/reverse-linked-list-ii/description/][https_leetcode-cn.com_problems_reverse-linked-list-ii_description]

#### 题目描述 ####

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

**说明**:  
1 ≤ m ≤ n ≤ 链表长度。

#### 示例 ####

输入: 1->2->3->4->5->NULL, m = 2, n = 4  
输出: 1->4->3->2->5->NULL

#### 解决方法 ####

分两步：(1)反转位置 m 到 n 的链表 (2)连接分割后的三段链表

/** * 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 (m==n || !head->next) return head;
            //(1)反转位置 m 到 n 的链表
            ListNode *begin=head; //找到反转开始的位置
            int count=1;
            while(count<m){ 
                count++;
                begin=begin->next;
            }
            ListNode *new_head=NULL;//进行反转
            ListNode *temp=NULL;
            int num=n-m+1;
            while(num--){ 
                temp = begin->next;
                begin->next = new_head;
                new_head = begin;
                begin = temp;
            }
            
            //(2)连接三段链表
            ListNode *pummyhead=head;
            if (m>1){ 
                while(head->next->next) head=head->next;
                head->next=new_head; 
            }
            else{ 
                pummyhead=new_head;
            }
            while(new_head->next) new_head=new_head->next;
            new_head->next=temp;
            
            return pummyhead;
        }
    };

[https_leetcode-cn.com_problems_reverse-linked-list-ii_description]: https://leetcode-cn.com/problems/reverse-linked-list-ii/description/