拓客网站建设,中国品牌网官方网站,上海建筑公司排行榜,石材外贸在哪个网站做#x1f6a9;本文已收录至算法学习之旅 一.基础反转
我们通常有两种方法反转链表#xff0c;一种是直接操作链表实现反转操作#xff0c;一种是建立虚拟头节点辅助实现反转操作。
力扣习题链接#xff1a;206. 反转链表
(1) 直接操作实现反转
我们需要一个变量pre来保… 本文已收录至算法学习之旅 一.基础反转
我们通常有两种方法反转链表一种是直接操作链表实现反转操作一种是建立虚拟头节点辅助实现反转操作。
力扣习题链接206. 反转链表
(1) 直接操作实现反转
我们需要一个变量pre来保存当前节点的上一个节点否则无法进行反转操作也就是指向上一个节点。我们还需要一个节点next来保存当前节点的下一个节点因为我们一旦操作当前节点的指针域后将会丢失下一个节点的地址。知道需要两个变量进行辅助接下来我们就可以严格按照一定的顺序来反转指针的。1.先记录当前节点的下一个指针不记录将会在下一步操作中丢失 2.令当前节点指向前一个节点如此我们便完成了这两个节点的反转操作可以开始移动指针进行下两个节点之间的操作 3.令pre指针指向当前指针移动后当前指针变成了前一个指针用于后续节点的反转4. 将当前指针移向下一个指针正是我们通过next变量保存了才能找到当前节点的下一个指针否则就在第2步中丢失了后续节点5.如此往复直到当前指针移动到null我们也完成了反转操作。 public ListNode reverseList(ListNode head) {// 记录前一个节点ListNode prev null;ListNode curr head;while (curr ! null) {// 记录后一个节点ListNode next curr.next;// 令当前节点指向前一个节点curr.next prev;// 保存当前节点prev curr;// 移动到下一个节点curr next;}return prev;}强烈建议各位手动模拟注意链表节点与节点之间是如何进行链接的体会每个变量的作用示意图如下
(2) 虚拟节点辅助实现反转
在上一篇中我们发现处理头节点与中间节点和尾部节点方法不一致如果单独处理则比较麻烦因此我们可以先建立一个虚拟头节点并且指向链表头节点head这样我们的操作便统一了。通过使用虚拟节点辅助实现反转我们可以每次从旧的链表拆下来一个结点接到ans后面然后将其他线调整好就可以了。
public static ListNode reverseList(ListNode head) {ListNode ans new ListNode(-1);ListNode cur head;while (cur ! null) {ListNode next cur.next;cur.next ans.next;ans.next cur;cur next;}return ans.next;
}与直接反转类似强烈建议各位手动模拟注意链表节点与节点之间是如何进行链接的体会每个变量的作用示意图如下 二.经典问题分析
(1) 指定区间反转
力扣链接反转链表 II 解决这道题目我们有两种方法一种是头插法一种是穿针引线法。
(1.1) 头插法
头插法反转的整体思想在需要反转的区间里每遍历到一个节点让这个新节点来到反转部分的起始位置。 这个插入过程就是前面所学习的带虚拟结点的插入操作每走一步都要考虑各种指针怎么指既要将结点摘下来接到对应的位置上还要保证后续结点能够找到。
public ListNode reverseBetween(ListNode head, int left, int right) {// 设置 dummyNode 是这一类问题的一般做法(统一节点不同位置处理)ListNode dummyNode new ListNode(-1);dummyNode.next head;ListNode pre dummyNode;// 找到待反转区间的前一个节点for (int i 0; i left - 1; i) {pre pre.next;}// 指向反转区间的起始节点ListNode cur pre.next;ListNode next;// 遍历区间内的节点并将其移向待反转区间的起始位置for (int i 0; i right - left; i) {next cur.next;cur.next next.next;next.next pre.next;pre.next next;}return dummyNode.next;
}(1.2) 穿针引线法
穿针引线法的整体思想首先找到待反转区间的开始节点与结束节点以及反转区间的前一个节点以及后一个节点。将区间内节点进行反转最后再按照我们记录的标识点进行连接即可。 public ListNode reverseBetween(ListNode head, int left, int right) {// 因为头节点有可能发生变化使用虚拟头节点可以避免复杂的分类讨论ListNode dummyNode new ListNode(-1);dummyNode.next head;ListNode pre dummyNode;// 第 1 步从虚拟头节点走 left - 1 步来到 left 节点的前一个节点for (int i 0; i left - 1; i) {pre pre.next;}// 第 2 步从 pre 再走 right - left 1 步来到 right 节点ListNode rightNode pre;for (int i 0; i right - left 1; i) {rightNode rightNode.next;}// 第 3 步切出一个子链表ListNode leftNode pre.next;ListNode succ rightNode.next;// 模拟设置为链表末尾节点指向nullrightNode.next null;// 第 4 步反转链表的子区间reverseLinkedList(leftNode);// 第 5 步接回到原来的链表中pre.next rightNode;leftNode.next succ;return dummyNode.next;
}// 反转链表private void reverseLinkedList(ListNode head) {ListNode pre null;ListNode cur head;while (cur ! null) {ListNode next cur.next;cur.next pre;pre cur;cur next;}}(2) 两两交换链表中的节点
力扣链接两两交换链表中的节点 当链表存在两个及以上未遍历到的节点时我们按照如下步骤模拟反转就行了。示意图如下 public ListNode swapPairs(ListNode head) {ListNode dummyNode new ListNode();dummyNode.next head;ListNode cur dummyNode.next,pre dummyNode;//在至少存在两个节点时进行翻转while(cur ! null cur.next ! null){ ListNode next cur.next;cur.next next.next;next.next cur;pre.next next;pre cur;cur cur.next;}return dummyNode.next;}(3) 两数相加
力扣链接: 两数相加 II 我们可以用栈轻松解决就不在此赘述代码实现先将两个链表的元素分别压栈然后再一起出栈将两个结果分别计算。之后对计算结果取模模数保存到新的链表中进位保存到下一轮。以此往复即可。
我们主要讲解如何针对链表操作由于本题的链表从首到尾刚好是从最高位到最低位而我们正常加法运算都是最低尾开始计算的因此我们需要先将两条链表进行反转操作然后再同时遍历每一位模拟加法运算即可轻松解决问题。
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {// 定义虚拟头节点开始记录新链表ListNode ans new ListNode();// 反转两条链表ListNode rl1 reverseListNode(l1);ListNode rl2 reverseListNode(l2);// 记录进位int add 0;// 链表不为空进位不为0则持续计算while (rl1 ! null || rl2 ! null || add ! 0) {int sum 0;// 若不为空则累加上该节点的值同时后移一位if (rl1 ! null) {sum rl1.val;rl1 rl1.next;}if (rl2 ! null) {sum rl2.val;rl2 rl2.next;}// 加上上一轮的进位sum add;// 记录本轮的进位add sum / 10;// 计算进位后的数sum % 10;// 从低位到高位拼接新的链表// ans - 0 - 7 8 ans - 8 - 0 - 7 ListNode node new ListNode(sum);node.next ans.next;ans.next node;}return ans.next;}// 直接操作反转链表public static ListNode reverseListNode(ListNode head) {ListNode pre null;while (head ! null) {ListNode next head.next;head.next pre;pre head;head next;}return pre;}
}(4) 回文链表
力扣链接:回文链表 在上一篇中我们讲解了判断回文链表可以使用集合双指针或者栈来解决我们还可以通过将双指针反转一半链表再进行比较判断来实现。
class Solution {public boolean isPalindrome(ListNode head) {if (head null) {return true;}// 找到前半部分链表的尾节点并反转后半部分链表ListNode firstHalfEnd endOfFirstHalf(head);ListNode secondHalfStart reverseList(firstHalfEnd.next);// 判断是否回文ListNode p1 head;ListNode p2 secondHalfStart;boolean result true;while (result p2 ! null) {if (p1.val ! p2.val) {result false;}p1 p1.next;p2 p2.next;} // 还原链表并返回结果firstHalfEnd.next reverseList(secondHalfStart);return result;}// 反转链表private 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;}// 通过双指针找到后半部分第一个节点private ListNode endOfFirstHalf(ListNode head) {ListNode fast head;ListNode slow head;while (fast.next ! null fast.next.next ! null) {fast fast.next.next;slow slow.next;}return slow;}
}(5) K 个一组翻转链表
力扣链接K 个一组翻转链表 这一题其实可以看做是指定区间反转的进阶形式只要我们足够细心其实这一题并不难。我们同样要使用到穿针引线法来解决问题相当于使用穿针引线法反转若干个指定区间。 public ListNode reverseKGroup(ListNode head, int k) {ListNode dummyNode new ListNode();dummyNode.next head;// 记录穿针引线法需要使用的四个标记点ListNode pre dummyNode, right, left, succ;// 反转若干个指定区间while (true) {right pre;// 1.寻找到反转区间right节点for (int i 0; i k; i) {// 当一组不足k个时表明不需要反转了直接返回结果if (right.next null) {return dummyNode.next;}right right.next;}// 2.记录left节点以及succ节点left pre.next;succ right.next;// 3.反转指定区间right.next null;right reverse(left);// 4.穿针引线拼接链表pre.next right;left.next succ;// 5.更新为下一个区间的起始节点的前一个节点pre left;}}// 反转链表public static ListNode reverse(ListNode head) {ListNode pre null;while (head ! null) {ListNode next head.next;head.next pre;pre head;head next;}return pre;}
