每日一题1-反转链表 II

92. 反转链表 II

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

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

示例:

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

条件：m n head
返回：部分翻转

2 思路

直接尝试理解，最终都卡住了

1. 链表o(1) insert 操作 ，我想到知识点是 遍历倒叙插入，以前做过这个题目，大学知识
   直接用在这个题目上，结果反而实现不了
2. reids 涉及一个就是在前面插入
3. 困难，最后一个n位置如何拼接起来
   寻找n位置，然后倒叙m个，然后拼接

绘制过程图：

第一个节点反转 全部过程

复杂度

时间：o(n)
链表插入 o(1)

image.png

代码位置

https://github.com/wangcy6/leetcode/blob/master/c%2B%2B/92.%20Reverse%20Linked%20List%20II_list_015.cpp

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        
        //输入数据都是合法的，不担心
        if(NULL ==head ||NULL ==head->next || m>=n)
        {
            return head;
        }
        
        //m=1时候，m非1时候虽然都是inert。区别head之前还是head之后，
        //标准reids等采用head之后。 一般我也是这样做的，head之前做法上学的。head会频繁的变化。
        //依赖头节点。stl还是其他设计都是一个头节点，方面操作 第一个节点不存入任何信息。
        //链表插入，故意构造一个存在head节点。 解决m数据不确定的情况。
        
        //head 指向第一数据记录，如果翻转的head位置不断发生变化不固定。
        //增加一个带头节点的单链表 减少复杂性操作
        //一般(redis,stl)链表插入都是head之后插入。head指向头节点
        
        ListNode dump(0); //固定的head节点。
        dump.next=head; //加入m=0的话,保持pStart存咋，固定不变。
        
        ListNode*pStart=&dump;
        ListNode*pEnd=head;
        ListNode*pCur=head;

        
        //移动m位置
        for(int i=1;pEnd&&i<m;i++)
        {
            pStart=pStart->next;
            pEnd=pEnd->next;
        }
        // 此时 i=m pStart(m-1)  pEnd(m)
        //排除了m=1时候，不进入循环的情况。 pStart为null
        
        
        //翻转 m到n
        
        for(int i=m;pCur&&i<n;i++)
        {
            pCur=pEnd->next;//需要翻转的节点 / A-B-C-D
            pEnd->next=pEnd->next->next;//循环的下一个节点  A-B-D
            
            pCur->next=pStart->next;// C-B-D
            pStart->next=pCur;//A-C-B-D
        }
        
        return dump.next;
        
    
    }
};

https://github.com/wangcy6/leetcode/blob/master/go/92_Reverse%20LinkedII_list_015.go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, m int, n int) *ListNode {
    
    if head ==nil || m>=n{
      return head
    }
    
    var dump ListNode
    dump.Next=head;
    start:=&dump //不区分m=1 还是非1
    
    for i:=1;i<m;i++{
        start=start.Next // 移动m-个位置
    }
    
    end:=start.Next
    
    //n-m-1 记录
    for i:=m;i<n;i++{
        
        cur:=end.Next
        end.Next=end.Next.Next
        
        cur.Next=start.Next
        start.Next=cur
        
    }
    
    return dump.Next
    
}

总结

总耗时：3天
直接看不绘制过程图，就被自己假设个问题吓住
例如，如果拼接翻转后面的链表这个问题。原来思路错误了。结果卡住了2天。