个人网站盈利,微信网站怎么做的好名字吗,政务服务和数字化建设局网站,建筑设计规范文章目录 前言一、两数相加1, 题目2, 思路分析2,1 找到中间结点2.2, 逆序后半段链表2.3, 合并两个链表 3, 代码 前言 各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你: #x1f4d5; JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管… 文章目录 前言一、两数相加1, 题目2, 思路分析2,1 找到中间结点2.2, 逆序后半段链表2.3, 合并两个链表 3, 代码 前言 各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你: JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等 Java数据结构: 顺序表, 链表, 堆, 二叉树, 二叉搜索树, 哈希表等 JavaEE初阶: 多线程, 网络编程, TCP/IP协议, HTTP协议, Tomcat, Servlet, Linux, JVM等(正在持续更新) 对于链表题, 常用的技巧和操作是: 头插, 尾插, 快慢双指针, 傀儡节点 一、两数相加
1, 题目
OJ链接
题目规定不能改变链表里的值, 而是真正交换链表节点 2, 思路分析
首先, 按照题意画出重排之后的链表, 观察原链表和重排之后的链表有什么变化 只看橙色结点, 发现后半段链表是逆序的
至此 本题的思路就非常清晰了
1, 找到中间节点(快慢双指针)2, 逆序后半段链表(傀儡头节点 头插)3, 合并两个链表(傀儡头结点 双指针)
注意本题没有返回值, 所以第三步操作之后不是返回新的头结点, 而是要修改原链表的头结点 head 之后的结点的指向
2,1 找到中间结点
1, 定义 slow 和 fast 两个指针, 起始位置都指向头结点2, slow 每次走一步, fast 每次走两步3, 当 fast 为 null 或 fast.next 为 null 时退出循环 如果有奇数个结点, slow 刚好是中间结点, 如果是偶数个结点, slow 是偏右的中间节点 2.2, 逆序后半段链表
1, 定义一个傀儡节点 pHead2, 定义一个 target 指针, target 就指向刚才的 slow3, 定义一个 next 指针, 记录 target 的下一个结点4, 循环遍历后半段链表, 依次头插到 pHead 所在的链表 此时 target 为 null, 逆序完成, 退出循环 这里有个 bug ! 在循环逆序链表之前应该先断开原链表的前半段和后半段 否则逆序完成之后, 原链表并没有断开, 再执行第三步 (合并两个链表) 时就会发生死循环! 所以在第一步时应该定义一个 prev 指针, 记录 slow 结点的前一个结点, 找到中间结点后, 令 prev.next null 2.3, 合并两个链表
1, 定义一个傀儡节点 ret2, 定义一个 cur1 指针, 指向原链表头结点 head3, 定义一个 cur2 指针, 指向逆序后的链表的头结点4, 定义一个 cur3 指针, 指向 ret
1, cur1 尾插到 cur3 后面
(此时 1 这个结点还指向 2 ), cur2 尾插到 cur3 后面 2, (此时 6 这个结点还指向 5 ), cur1 尾插到 cur3 后面, (此时 2 这个结点还指向 3 ), cur2 尾插到 cur3 后面 3, (此时 5 这个结点还指向 4 ), cur1 尾插到 cur3 后面
cur2 尾插到 cur3 后面 4, 得到整个链表, 此时 head 结点还在, 并且 head 之后的结点链表结构已经被修改成功
在一次循环中, 先尾插 cur1, 再尾插 cur2, 循环条件设为 cur1 ! null 即可
因为 : 如果链表是偶数个结点, 链表前半段和后半段长度相同, 如果链表是奇数个结点, 链表前半段比后半段少一个结点, 但没关系, 尾插时不会改变结点的的 next 域 3, 代码 public void reorderList(ListNode head) {if(head null || head.next null) {return;}// 1, 找到中间节点ListNode slow head;ListNode fast slow;ListNode prev head;while(fast ! null fast.next ! null) {prev slow;slow slow.next;fast fast.next.next;}ListNode target slow;prev.next null;ListNode phead new ListNode(0);ListNode cur phead;// 2, 逆序后半个链表while(target ! null) {ListNode next target.next;target.next cur.next;cur.next target;target next;}ListNode cur1 head;ListNode cur2 phead.next;ListNode ret new ListNode(0);ListNode cur3 ret;// 3, 合并链表while(cur1 ! null){cur3.next cur1;cur3 cur3.next;cur1 cur1.next;cur3.next cur2;cur3 cur3.next;cur2 cur2.next;}}
