做酒水网站有哪些,单色系网站设计有哪些,自己怎么做商城网站,南京百度提升优化目录 力扣题目地址#xff1a; 题目#xff1a; 那我们直接看题解吧#xff1a; 解题方法#xff1a; 难度分析#xff1a; 审题目事例提示#xff1a; 解题分析#xff1a; 解题思路#xff1a; 解题补充#xff1a; 力扣题目地址#xff1a; 143. 重排链表 - 力扣 题目 那我们直接看题解吧 解题方法 难度分析 审题目事例提示 解题分析 解题思路 解题补充 力扣题目地址 143. 重排链表 - 力扣LeetCode 难度中等 今天刷重排链表大家有兴趣可以点上看看题目要求试着做一下。
题目 给定一个单链表 L 的头节点 head 单链表 L 表示为 L0 → L1 → … → Ln-1 → Ln 请将其重新排列后变为 L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → … 不能只是单纯的改变节点内部的值而是需要实际的进行节点交换。 那我们直接看题解吧 解题方法 方法1、线性表双指针 方法2、寻找链表中点链表逆序链表合并 难度分析 解题方法需要综合使用有一定难度 审题目事例提示 ·不能只是单纯的改变节点内部的值而是需要实际的进行节点交换。 ·不用进行return返回修改后的链表 解题分析 由于链表不支持下标访问所以我们无法随机访问链表中任意位置的元素。 因此比较容易想到的一个方法是我们利用线性表存储该链表然后利用线性表可以下标访问的特点直接按顺序访问指定元素重建该链表即可。 解题思路 1、判断链表是否为空空则直接return即链表无意义结束方法 2、创建线性表list,创建节点node,初始化指向链表head 3、循环遍历链表依次将链表节点添加到线性表中 4、创建双指针并初始化left0rightlist.size()-1 5、利用while循环根据题目规则对链表进行移动排序移动节点主要改变指针指向即可 6、最后让最后一个节点指针指向null即可 代码实现
class Solution {public void reorderList(ListNode head) {if (head null) { //进行判空操作return;}//创建线性表对象存储类型为ListNodeListListNode list new ArrayListListNode();ListNode node head; //链表创建节点指向headwhile (node ! null) { list.add(node);node node.next;}int i 0, j list.size() - 1; //创建双指针while (i j) {list.get(i).next list.get(j);i;if (i j) { //如果指针相等则退出循环break;}list.get(j).next list.get(i);j--;}list.get(i).next null; //最后指针指向null}
}解题补充 实际上相当于定义一个ArrayList的顺序表存储对象类型为ListNode类型先把链表的结点都填充到顺序表中然后利用顺序表的get方法获取结点然后对结点的指针进行修改最终修改的还是链表只是利用了顺序表的get方法来快速定位到目标结点。 代码实现方法2
class Solution {public void reorderList(ListNode head) {if (head null) {return;}ListNode mid middleNode(head);ListNode l1 head;ListNode l2 mid.next;mid.next null;l2 reverseList(l2);mergeList(l1, l2);}public ListNode middleNode(ListNode head) {ListNode slow head;ListNode fast head;while (fast.next ! null fast.next.next ! null) {slow slow.next;fast fast.next.next;}return slow;}public ListNode reverseList(ListNode head) {ListNode prev null;ListNode curr head;while (curr ! null) {ListNode nextTemp curr.next;curr.next prev;prev curr;curr nextTemp;}return prev;}public void mergeList(ListNode l1, ListNode l2) {ListNode l1_tmp;ListNode l2_tmp;while (l1 ! null l2 ! null) {l1_tmp l1.next;l2_tmp l2.next;l1.next l2;l1 l1_tmp;l2.next l1;l2 l2_tmp;}}
}
