leetcode 92. 反转链表 II-蒲公英云

leetcode 92. 反转链表 II

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

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

示例:

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

思路： dfs+回溯时修改链表

我觉得没啥可以分析的。只要理解了dfs的过程，然后稍微处理一下边界条件即可。

/**
 * 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 *ans = new ListNode(0);
        ListNode *p=head;
        ListNode *q=NULL;
        ListNode *last=new ListNode(0);
        int k=1;
        while(k<m)
        {
            q=p;
            p=p->next;
            k++;
        }
        //cout<<k<<endl;
        dfs(p,NULL,ans,last,m,n,k);
        //cout<<last->val<<endl;
        if(q==NULL) return ans;
        else q->next=ans;
        return head;
    }
     void dfs(ListNode *head,ListNode *pre,ListNode *&ans,ListNode *&last, int m,int n,int k)
    {
        if(k<=n)
        {
            int tmp=k;
            tmp++;
            dfs(head->next,head,ans,last,m,n,tmp);
        }
        if(k==n) ans=head;
        if(k==n+1)
        {
            last=head;
            return;
        }
        if(k==m)
        {
            head->next=last;
            return;
        }
        head->next=pre;
    }
};