【leetcode刷题】T105-反转链表 II

【题目】反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。说明:
1 ≤ m ≤ n ≤ 链表长度。示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
【思路】本题相较于【T104-翻转链表】，增加两项内容：一是需要找到要翻转的节点，二是需要保存链表左侧最后一个非翻转节点，用于修改指针。【代码】python版本# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        if not head or not head.next or m == n:
            return head
        
        # 添加一个节点
        add = ListNode(0)
        add.next = head
        head = add
        
        count = 1
        p = head
        
        while p:
            if count == m:
                break
            p = p.next
            count += 1
            
        # 记录最后一个未旋转的节点
        add = p
        p = p.next
        q = p.next
        r = q.next
        while q:
            if count == n:
                break
            r = q.next
            q.next = p
            p = q
            q = r
            count += 1
        
        # 修改头尾指针
        add.next.next = r
        add.next = p
        
        return head.next
C++版本/**
 * 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 || !head->next || m == n)
            return head;
        // 添加一个节点
        ListNode* add = new ListNode(0);
        add->next = head;
        head = add;
        
        // 找到节点
        ListNode* p = head;
        ListNode* q;
        ListNode* r;
        int count = 1;
        while(p){
            if(count == m)
                break;
            else{
                count++;
                p = p->next;
            }
        }
        
        // 记录最后一个未翻转的元素
        add = p;
        p = p->next;
        if(p->next)
            q = p->next;
        else
            return head->next;
        
        // 翻转
        while(true){
            if(count == n)
                break;
            r = q->next;
            q->next = p;
            p = q;
            q = r;
            count++;
        }
        
        // 修改指针
        add->next->next = r;
        add->next = p;
        
        return head->next;
    }
};