[leetcode篇]重排链表

ky0ncheng 发布于2021-09-10 10:50 / 1694人阅读

摘要：首先把先半段链表和后半段链表的头节点和连接起来，在把处于在第二个位置节点的和连接起来，最后把两个尾节点连接和起来因此最后的链表节点顺序为。

文章目录

❤️问题描述：

❤️算法思想：

?题目解读：

我们看看此题，是不是起先一点思路都没有呀！！！其实此题并不难，关键在于我们一定要读懂题目，题目是这样把链表后半段的val值，移到链表的前半段，并且是这样的前半段的一个节点，后半段一个节点，前半段一个节点·····

?具体解析：

首先链表分为两半，利用快慢指针思想，快指针一次遍历链表中的两个节点，慢指针一次遍历链表中一个节点，当快指针把链表遍历完时，慢指针恰好指向链表的中间节点。然后把中间节点之后的链表断开，生成两个子链表。
翻转中间节点之后的链表，因为在题目中从后向前遍历链表把后半段的链表节点插入到前半段节点中,在这里翻转链表的具体步骤不加以赘述，详细请看博客链表习题
翻转链表之后，例如看图说话中，链表后半段节点的顺序就变成6,5,4,最后从链表的前半段链表和后半段链表的节点开始，逐个把他们的节点相连成为一个新的链表。首先把先半段链表和后半段链表的头节点1和6连接起来，在把处于在第二个位置节点的2和5连接起来，最后把两个尾节点连接3和4起来因此最后的链表节点顺序为1,6,2,5,3,4。
如果原链表的个数为奇数时，前半段链表比后半段链表多一个节点，所以说在两个子链表等分连接完成后，前半段链表还不能为空，所以在连接的链表之后添上多出的节点。

?看图说话：

?代码实现：

//翻转链表 public Node reverseList(Node node){            Node newhead = null;            Node cur = node;            while(cur!=null){                //保存节点                Node curNext = cur.next;                cur.next = newhead;                newhead = cur;                cur = curNext;            }            return newhead;        }        public Node reorderList() {            //首先设置快慢指针，快慢指针遍历链表，慢指针一次遍历一个节点，快指针一次遍历两个节点，所以说当快指针把链表遍历          //完时，慢指针刚好走到了链表的一半            Node dummy = new Node(0);            dummy.next = head;            Node fast = dummy;            Node slow = dummy;            while (fast != null && fast.next != null) {                fast = fast.next.next;                slow = slow.next;            }            //找到中间节点，然后从中间断开链表            Node temp = slow.next;            slow.next = null;           return  reSortList(head,  reverseList(temp),dummy);        }        public Node reSortList(Node node1,Node node2,Node head){            Node prev = this.head;            while(node1 != null && node2 != null){            //保存遍历节点                Node temp = node1.next;                prev.next = node1; //node2节点连接node1节点                node1.next = node2;//node1节点连接node2节点                prev = node2;// 更新prev                                //遍历子链表                node1 = temp;                node2 = node2.next;            }            //如果原链表节点个数为奇数时           if(node1!=null){               prev.next = node1;           }            return head;        }

服务器托管混合云 Leetcod LeetCode LeetCode_String leetcode_35_SearchIn

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/119775.html

LeetCode 剑指 Offer II 链表（021-029）

摘要：说明不允许修改给定的链表。注意，函数返回结果后，链表必须保持其原始结构。示例输入输出解释相交节点的值为注意，如果两个链表相交则不能为。将这两数相加会返回一个新的链表。 ...

不知名网友 2021-11-29 10:50 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月汇总（55 题攻略）

摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目录不...

warmcheng 2019-08-26 10:09 评论0 收藏0
Leetcode：刷完31道链表题的一点总结

摘要：既然说到地址空间了就顺带说一下上面环形链表这道题的另一种很的解法吧。介绍完常规操作链表的一些基本知识点后，现在回到快慢指针。前几天第一次在 Segmentfault 发文—JavaScript：十大排序的算法思路和代码实现，发现大家似乎挺喜欢算法的，所以今天再分享一篇前两个星期写的 Leetcode 刷题总结，希望对大家能有所帮助。本文首发于我的blog 前言今天终于...

DevTalking 2019-08-23 17:50 评论0 收藏0
LeetCode.2 两数相加(Add Two Numbers)(JS)

摘要：更新之前说感觉优秀答案的最后三行可以用尾递归优化不知道尾递归的小伙伴可以点这里，仔细想了一下，并不能。尾递归的实现，往往需要改写递归函数，确保最后一步只调用自身。上周日就想写vue.nextTick的源码分析，可是总是不知道从哪儿下手，今天有时间，先把leetcode第二题补了，感觉这道题还挺简单的一、题目两数相加：给出两个非空的链表用来表示两个非负的整数。其中，它们各自...

Binguner 2019-08-23 16:26 评论0 收藏0
数据结构之链表OJ练习检验你的链表水平是否合格

摘要：同时让当前结点的指针指向，从而实现从链表尾部开始的局部反转当递归函数全部出栈后，链表反转完成。这个链表的倒数第个节点是值为的节点。新链表是通过拼接给定的两个链表的所有节点组成的。目录 1.反转链表 K个一组翻转链表链表的中间节点：链表倒数第k个节点：删除链表倒数第k个节...

andycall 2021-11-25 09:43 评论0 收藏0