-
链表不得不刷的进阶题目，牛客TOP101链表相关——链表刷题
前言：
紧承上一篇 链表基础题目分享 的博客，本篇博客题目多来自于牛客 TOP101 中链表相关，难度较上一篇稍难半分。博主希望通过言简意赅的思路和代码，为大家提供不同的解题灵感，受限于精力原因只有少部分题目包含了详细图解，很抱歉，后续可能会进行补全。期盼能大家能在下面的链表题解中有所启发思考，共勉。
目录：
1 链表内指定区间反转
1）思路：
（1）区间头插：
-
添加表头节点newHead，结果返回 newHead.next
-
初始化pre，cur，pre cur再向前, m - 1 步到达反转区间
- pre保存 m节点的上一个节点（m节点会随头插发生变化），cur节点保存第一次到达m位置的节点
-
将 区间内元素进行头插
- 保存 curNext
- cur 移向curNext.next
- 配合 pre 将 curNext 进行头插
（2） 递归尾插:
图示
-
reverseBetween 递归, 找到反转区间
- 子问题思路, 直到 m == 1 找到反转区间
- 中止条件: m == 1 开始进行reverse 反转
- 本级目标: 不断缩短区间, 将本级节点 head 和子问题中反转后的子链表进行拼接
- 返回值: 返回拼接后的新链表的头结点
-
reverse 递归, 进行 “尾插” 反转
- 子问题思路, 直到 n == 1 找到 n 节点开始 “归” 进行尾插
- 中止条件: n == 1 找到 n 节点, 同时保存 n 节点下一个节点
- 本级目标: 缩短 n 值, 子问题结束后将本级节点 head 尾插到 n 节点之后
- 返回值: 返回子问题反转后的头结点, 也就是未反转区间的 n 节点
2）解法：
- 区间头插
public ListNode reverseBetween (ListNode head, int m, int n) { // write code here //最后返回 表头节点的下一个节点即可，因为 head 位置可能会发生改变 ListNode newHead = new ListNode(-1); newHead.next = head; //通过pre 节点可以找到上一次移向 m 位置的节点 ListNode pre = newHead; ListNode cur = head; //到达 m 节点 for(int i = 1; i < m; i++){ pre = cur; cur = cur.next; } //将区间内元素进行头插 //通过改变 cur.next 达到cur向前移动的目的，且保持 cur 内容不变 for(int i = m; i < n; i++){ //cur 向前移动 ListNode curNext = cur.next; cur.next = curNext.next; //curNext 进行头插 curNext.next = pre.next; pre.next = curNext; } return newHead.next; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 递归尾插
public ListNode reverseBetween (ListNode head, int m, int n) { //m == 1到达反转区间,进行反转, 反转完成直接返回 if(m == 1){ return reverse(head, n); } //进入子问题,保存反转过后子链表的头结点 ListNode node = reverseBetween(head.next, m - 1, n - 1); //将本级节点和反转后子链表进行拼接 head.next = node; //返回拼接后的新链表的头结点 return head; } //n节点的 next 节点 public ListNode finalNext = null; public ListNode reverse(ListNode head, int n){ //到达最后一个节点直接返回, 同时保存 n 节点下一个节点 if(n == 1){ finalNext = head.next; return head; } //进入反转的子问题, 保存的 node 是未经过反转的 n 节点, 该节点也是区间所有节点反转完成后的 区间头结点 ListNode node = reverse(head.next, n - 1); //进行 "尾插" 反转, 因为本级节点 head 总是子区间反转过后 n 节点的上一个节点 head.next.next = head; //head 指向 finalNext 节点, 成为新的 n 节点 head.next = finalNext; //返回 区间头结点 return node; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
2 链表中的节点每k个一组翻转
1 ) 思路:
（1）求组数反转:
- 链表长度求反转组数 num
- 定义 cur pre 进行反转 num组
（2）递归:
- 中止条件: head == null 或者 反转次数不足 k 个
- 本级任务: cur pre 进行反转, 反转结束 pre 到达表头, head变成表尾, head.next 指向子问题返回的表头节点
- 返回值: 返回反转链表的头节点
2）解法:
- 求组数反转
public ListNode reverseKGroup (ListNode head, int k) { // write code here ListNode newHead = new ListNode(-1); newHead.next = head; //计算链表长度 算出反转次数 int count = 0; ListNode cur = head; while(cur != null){ cur = cur.next; count++; } int num = count / k; //遍历链表进行反转 ListNode pre = newHead; cur = head; for(int i = 0; i < num; i++){ pre = reverse(cur, pre, k); cur = pre.next; } return newHead.next; } public ListNode reverse(ListNode cur, ListNode pre, int k){ ListNode curNext = null; for(int i = 1; i < k; i++){ //cur 向前 curNext = cur.next; cur.next = curNext.next; //头插 curNext.next = pre.next; pre.next = curNext; } pre = cur; return pre; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 递归
public ListNode reverseKGroup (ListNode head, int k) { //链表反转的最后节点的下一个节点 ListNode tail = head; //中止条件, head 为空 或者 反转不足 k 个 for(int i = 0; i < k; i++){ if(tail == null){ return head; } tail = tail.next; } ListNode cur = head; ListNode pre = null; //进行反转 while(cur != tail){ ListNode curNext = cur.next; cur.next = pre; pre = cur; cur = curNext; } //头节点反转过后变为尾节点 指向下一个子问题求得反转链表的头结点 head.next = reverseKGroup(tail, k); //pre 节点变为反转过后的新链表头结点, 作为子问题的结果返回 return pre; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
3 合并两个排序的链表
1 ) 思路
（1）迭代
- 使用 带虚拟头结点 的新链表保存排序节点
- 带虚拟头结点链表保证每个节点都有前驱, 称为 “哨兵”
- 找到当前 list1.val 和 list2.val 的较小值保存到新链表中 (取等默认保存 list1.val) , list1 或 list2 向后, 如此 循环直到 list1 || list2 == null
- 将非空的 list1 / list2 拼接到新链表后面
（2）递归
- 中止条件: list1 / list2 == null
- 本级目标: 找到 当前 list1 和 list2 中最小的元素节点, 通过 子问题重构 当前最小节点的下一个节点
- 重构进行递归缩小查找区间
- 返回值: 返回最小节点,因为找到最小元素可能在 list1 也可能在 list2中,所以要 分开讨论返回不同值
2 ) 解法
- 迭代
public ListNode Merge(ListNode list1,ListNode list2) { //迭代 if(list1 == null) { return list2; } if(list2 == null){ return list1; } ListNode newHead = new ListNode(0); ListNode cur = newHead; while(list1 != null && list2 != null){ if(list1.val < list2.val){ cur.next = list1; list1 = list1.next; }else{ cur.next = list2; list2 = list2.next; } cur = cur.next; } if(list1 != null){ cur.next = list1; }else{ cur.next = list2; } return newHead.next; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 递归
public ListNode Merge(ListNode list1,ListNode list2) { //中止条件 list1 / list2 == null if(list1 == null) return list2; if(list2 == null) return list1; //找到 当前 list1 和 list2 中最小的元素节点, 递归缩小区间,找到当前最小节点的下一个节点 //子问题完成后返回新链表的头节点 if(list1.val <= list2.val){ list1.next = Merge(list1.next, list2); return list1; }else{ list2.next = Merge(list1, list2.next); return list2; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
4 合并k个已排序的链表
1 ) 思路:
（1）优先级队列
- 创建堆小堆保存每个链表头结点
- 使用比较器 new Comparator (){ @Override 重写compare} 创建小堆
- lambda表达式 (e1, e2) -> e1.val - e2.val 创建小堆
- 保存节点判空
- 出队,元素 放入新链表, 出队元素后继进行判空入队
（2） 归并排序
- 将 k 个元素看作 k 个子问题, 通过递归中 “递” 的过程 将区间缩小划分出子问题 (依靠下标进行划分), 到达 “归” 的过程将 子问题返回的链表两两一组进行合并, 成为一个新链表, 随后不断向上合并
- 中止条件: 只有一个节点或者 没有节点了
- 本级目标: 使用 mid 划分区间, 将 mid 分开的左右两区间进行子问题排序, 合并成两张表, 再将两新表进行合并
- 返回值: 合并完成后新链表的头结点
- tip:
- 子问题返回新链表 加上合并返回 可以优化成一步
- ArrayList 通过 get() 方法获取到下标元素
- 合并两链表可以使用递归进行
2 ) 解法:
- 优先级队列
public ListNode mergeKLists(ArrayList<ListNode> lists) { //1 创建堆小堆保存每个头结点 PriorityQueue<ListNode> minHeap = new PriorityQueue<>(new Comparator<ListNode>(){ @Override public int compare(ListNode e1, ListNode e2){ return e1.val - e2.val; } }); for(ListNode node : lists){ if(node != null) minHeap.offer(node); } //2 出队, 放入新链表, 判空入队 // 创建虚拟头结点 ListNode newHead = new ListNode(-1); ListNode cur = newHead; while(!minHeap.isEmpty()){ ListNode tmp = minHeap.poll(); ListNode tmpNext = tmp.next; // 放入新链表 cur.next = tmp; cur = cur.next; // 非空后继入队 if(tmpNext != null){ minHeap.offer(tmpNext); } } return newHead.next; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 归并排序
public ListNode mergeKLists(ArrayList<ListNode> lists) { //进行归并排序 return mergeSort(lists, 0, lists.size() - 1); } //排序 public ListNode mergeSort(ArrayList<ListNode> lists, int left, int right){ //中止条件为: 只有一个节点或者没有节点了 if(left > right) return null; if(left == right) return lists.get(left); //本级目标: 将 mid 分开的左右两区间进行子问题排序, 合并成两张表, 再将两新表进行合并 // 通过 mid 进行区间划分 int mid = (left + right) / 2; //对下面代码进行优化 //return merge(mergeSort(lists, left, mid), mergeSort(lists, mid + 1, right)); ListNode leftNode = mergeSort(lists, left, mid); ListNode rightNode = mergeSort(lists, mid + 1, right); //合并子问题返回的两链表的头结点 ListNode newNode = merge(leftNode, rightNode); //返回值: 新合并的链表头结点 return newNode; } //递归合并 public ListNode merge(ListNode list1, ListNode list2){ if(list1 == null) return list2; if(list2 == null) return list1; if(list1.val <= list2.val){ list1.next = merge(list1.next, list2); return list1; }else{ list2.next = merge(list1, list2.next); return list2; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
5 判断链表中是否有环
1）思路:
- 进行空节点 和 单节点的判断
- 快慢指针 不同速度向后移动, 以此循环
- 注意条件 fast != null && fast.next != null
2）解法:
- 双指针
public boolean hasCycle(ListNode head) { //解法1: 快慢指针 //1 判空 if(head == null || head.next == null) return false; //2 快慢指针 ListNode fast = head; ListNode slow = head; //3 向后移动 while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; if(fast == slow){ return true; } } return false; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
6 链表中环的入口结点
1）思路:
（1）双指针
- 先通过快慢指针判断是否有环
- 慢指针从头开始走, 快指针从相遇点走, 一次都走一步 再次相遇为入口点
- 有环的情况下, 从入口点走到相遇点 和 相遇点走到入口点的距离相等
（2）哈希
- 使用 HashSet 保存节点, 遇到重复节点直接返回, 直到遇到空节点
2）解法:
- 快慢指针
public ListNode EntryNodeOfLoop(ListNode pHead) { //1 快慢指针找到相遇点 ListNode tmp = hasCycle(pHead); if( tmp == null) return null; ListNode fast = tmp; ListNode slow = pHead; //2 慢指针从头开始走, 再次相遇为入口点 while(fast != slow){ fast = fast.next; slow = slow.next; } return slow; } public ListNode hasCycle(ListNode pHead){ ListNode fast = pHead; ListNode slow = pHead; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; if(fast == slow) return slow; } return null; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 哈希
public boolean hasCycle(ListNode head) { HashSet<ListNode> set = new HashSet<>(); while(head != null){ //有重复节点直接返回 if(set.contains(head)){ return true; } set.add(head); head = head.next; } return false; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
7 两链表的公共节点
1）思路:
- 利用链表公共节点后面等长的特性
- 思路1: 先求出链表差值,让长链表先走差值步, 在一起走找到公共节点
- 思路2: 先各自走完自己的链表, 走完后转向另一个链表, 直到找到相等节点(为 null 也可以返回)
2）解法:
- 差值法1
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { //1 求两链表长度差 ListNode cur1 = pHead1; ListNode cur2 = pHead2; int maxLen = 0; int minLen = 0; while(cur1 != null){ maxLen++; cur1 = cur1.next; } while(cur2 != null){ minLen++; cur2 = cur2.next; } //2 长链表先走差值步 cur1 = pHead1; cur2 = pHead2; if(maxLen < minLen){ cur1 = pHead2; cur2 = pHead1; } int sub = Math.abs(maxLen - minLen); while(sub > 0){ cur1 = cur1.next; sub--; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 差值法2
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { ListNode cur1 = pHead1; ListNode cur2 = pHead2; while(cur1 != cur2){ cur1 = cur1 == null ? pHead2 : cur1.next; cur2 = cur2 == null ? pHead1 : cur2.next; } return cur1; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
8 链表相加(二)
1）思路:
（1）反转链表法:
图示
- 先反转两条链表
- 创建虚拟头结点, 遍历反转后的双链表, 计算节点和, 创建节点保存到新链表中, 直到链表都为空
- 使用 三目表达式计算 每个节点的值 和 下一个节点
- 使用 一个 tmp 先计算节点和, 新节点添加完成后, 计算进位值进行保存
- 判断进位是否为空, 添加节点,
- 重新新反转链表 进行返回
2）解法:
public ListNode addInList (ListNode head1, ListNode head2) { ListNode cur1 = reverse(head1); ListNode cur2 = reverse(head2); ListNode dummy = new ListNode(-1); ListNode cur = dummy; //用于保存每个节点值 和 进位值 int tmp = 0; while(cur1 != null || cur2 != null){ int val1 = cur1 == null ? 0 : cur1.val; int val2 = cur2 == null ? 0 : cur2.val; //计算值,保存节点 tmp = val1 + val2 + tmp; ListNode node = new ListNode(tmp % 10); cur.next = node; cur = cur.next; //保存进位 tmp /= 10; cur1 = cur1 == null ? null : cur1.next; cur2 = cur2 == null ? null : cur2.next; } //判断进位是否为空 if(tmp != 0){ cur.next = new ListNode(tmp); } //最后再次反转 return reverse(dummy.next); } //反转链表 public ListNode reverse(ListNode root){ ListNode pre = null; ListNode rootNext = null; while(root != null){ rootNext = root.next; root.next = pre; pre = root; root = rootNext; } return pre; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
9 单链表的排序
1）思路:
（1）归并排序:
排序方法传入的 tail 参数为 null, 该节点会在 递的过程中被省略
- 中止条件: 没有元素 / 只有两个元素
- 子问题只有两个元素时, 由于本题使用 现有快慢指针 的特征, 必须将后一个元素进省略
- 但同时该节点未被舍弃, 相邻子问题头结点就是这个被舍弃的节点, 最后只有最后一个 tail 节点被省略, 但是 tail 又为空, 所以不影响结果
- 本级目标: 拼接两个子问题返回的排序过的新链表
- 返回值: 返回拼接后链表的头结点
（2）数组排序:
- 使用 ArrayList 保存链表节点值,
- 使用 Collection.sort() 进行排序
- 将值放回链表
2）解法:
- 归并排序
public ListNode sortInList (ListNode head) { // write code here //尾节点传入 null, 因为进行双指针二分过程中. 最后一个节点必定会被省略 return sort(head, null); } public ListNode sort(ListNode head, ListNode tail){ //中止条件 没有元素 / 只有两个元素 if(head == null)return head; //只有两个元素是会舍弃后一个元素, 但是在相邻子问题头结点就是这个被舍弃的节点 //如此迭代, 原链表的最后一个 tail 节点会舍弃, 但是 tail 节点又为空所以没有影响 if(head.next == tail){ //如果要进行链表合并 子链表势必是经过调整后的新链表, //如果next 带有原本旧链表的节点, 合并过程就无法顺利进行, 所以将 next置为空 head.next = null; return head; } //本级目标: 拼接两个子问题返回的排序过的新链表(逻辑上不被旧链表影响) // 快慢指针进行二分, 快指针到最后一个节点为止 slow 即是mid ListNode fast = head; ListNode mid = head; while(fast != tail){ fast = fast.next; mid = mid.next; if(fast != tail){ fast = fast.next; } } //返回值: 返回拼接后链表的头结点 return merge(sort(head, mid), sort(mid, tail)); // ListNode left = sort(head, mid); // ListNode right = sort(mid, tail); // ListNode node = merge(left, right); // return node; } public ListNode merge(ListNode list1, ListNode list2){ if(list1 == null) return list2; if(list2 == null) return list1; if(list1.val <= list2.val){ list1.next = merge(list1.next, list2); return list1; }else{ list2.next = merge(list1, list2.next); return list2; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 数组排序
public ListNode sortInList (ListNode head) { ArrayList<Integer> array = new ArrayList<>(); ListNode cur = head; while(cur != null){ array.add(cur.val); cur = cur.next; } Collections.sort(array); cur = head; for(int i = 0; i < array.size(); i++){ cur.val = array.get(i); cur = cur.next; } return head; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
10 链表奇数偶数重排
1）思路:
（1）双指针法
图示
- 初始化 奇数的指针 odd 和 偶数指针 end, 同时 保存偶数链表首节点 evenHead
- evenHead 最后要和 奇数链表进行拼接
- 连接过程中, 先进行奇数的连接, 再进行偶数的连接
- 进入循环, 奇数总在偶数之前
- odd.next = even.next 奇数指向偶数下一个节点, 再后移
- even.next = odd.next 偶数指向奇数下一个节点, 再后移
- 对于奇数链表来说, 无论节点个数是 奇 偶 个, 最后一次循环 奇 数节点都能指向带值的有效节点, 供后续进行拼接
- 对于偶数链表来说, 节点奇数个时, 最后一次循环 偶数节点指向空节点; 节点为偶数个时, 最后一次循环 偶数节点指向原链表的最后一个节点, 最后节点下一个还是为空节点, 所以 偶数链表最后始终为空节点
- 奇数偶数链表进行拼接, 返回 head
- 非空奇数节点指向 偶数节点头结点 evenHead
2）解法:
- 双指针
public ListNode oddEvenList (ListNode head) { // write code //1 判空 初始化 odd even evenHead if(head == null) return head; ListNode odd = head; ListNode even = head.next; ListNode evenHead = even; //2 进行奇数偶数链表的分别连接 while(even != null && even.next != null){ //奇数再偶数前面, 先进行奇数连接 odd.next = even.next; odd = odd.next; //再进行偶数连接 even.next = odd.next; even = even.next; } //3 奇数偶数链表进行拼接 返回 head odd.next = evenHead; return head; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
文章至此就结束啦，如果看官朋友觉得还不错，博主求 点赞、评论、收藏 三连，十分感谢
奇数总在偶数之前- odd.next = even.next 奇数指向偶数下一个节点, 再后移
- even.next = odd.next 偶数指向奇数下一个节点, 再后移
- 对于奇数链表来说, 无论节点个数是 奇 偶 个, 最后一次循环 奇 数节点都能指向带值的有效节点, 供后续进行拼接
- 对于偶数链表来说, 节点奇数个时, 最后一次循环 偶数节点指向空节点; 节点为偶数个时, 最后一次循环 偶数节点指向原链表的最后一个节点, 最后节点下一个还是为空节点, 所以 偶数链表最后始终为空节点
- 奇数偶数链表进行拼接, 返回 head
- 非空奇数节点指向 偶数节点头结点 evenHead
2）解法:
- 双指针
public ListNode oddEvenList (ListNode head) { // write code //1 判空 初始化 odd even evenHead if(head == null) return head; ListNode odd = head; ListNode even = head.next; ListNode evenHead = even; //2 进行奇数偶数链表的分别连接 while(even != null && even.next != null){ //奇数再偶数前面, 先进行奇数连接 odd.next = even.next; odd = odd.next; //再进行偶数连接 even.next = odd.next; even = even.next; } //3 奇数偶数链表进行拼接 返回 head odd.next = evenHead; return head; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
文章至此就结束啦，如果看官朋友觉得还不错，博主求 点赞、评论、收藏 三连，十分感谢
-
-
相关阅读:
爬虫兽问题解答1-抖音评论区爬虫采集拓客系统
Text-to-SQL小白入门（四）指令进化大模型WizardLM
走近科学之《spring security 的秘密》
学redis看这里就行了
ENVI_classic报错
Java当中的数组的定义与简单使用
LInux相关操作命令
七月论文审稿GPT第2版：从Meta Nougat、GPT4审稿到Mistral、LongLora
php上传图片，yii上传图片，（base64上传）
ros gdb调试
- 原文地址：https://blog.csdn.net/honglan297/article/details/126376578
