首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >每日一题-反转链表

每日一题-反转链表

作者头像
程序员小王
发布2019-05-17 14:22:28
4660
发布2019-05-17 14:22:28
举报
文章被收录于专栏:架构说架构说
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)

o(n)

代码位置

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

}
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-05-14,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Offer多多 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 2 思路
  • 复杂度
    • 代码位置
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档