当前位置：首页 > news >正文

Leetcode328奇偶链表，Leetcode21合并两个有序链表，Leetcode206反转链表三者综合题

news 2024/11/5 1:52:53

题目描述

思路分析

这题的思路就和我们的标题所述一样，可以看作是这3个题的合并，但是稍微还有一点点区别
比如：奇偶链表这道题主要是偶数链在了奇数后面，字节这个的话是奇偶链表分离了
所以字节这题的大概思路就是：

将奇偶链表分离，反转偶链表，然后将反转后的偶链表和奇链表进行合并（也就是合并两个有序链表）

总体来说不是很难，思路也比较清晰，还是比较好实现的

不得不说大厂的题还是考的全面，一个题考了3个知识点

代码实现

public ListNode sortLinkedList(ListNode head) {if(head == null || head.next == null) {return head;}// 分离链表为单索引和双索引两个子链表, 并返回链表的头节点，0 - oddHead, 1 - evenHeadList<ListNode> heads = splitLists(head);// 反转双索引子链表（递减顺序）变为递增顺序ListNode reversedEven = reverse(heads.get(1));// 合并两个递增子链表ListNode mergedHead = mergeTwoSortedLists(heads.get(0),reversedEven);return mergedHead;}public List<ListNode> splitLists(ListNode head){List<ListNode> heads = new ArrayList<>();ListNode oddHead = new ListNode(0);ListNode evenHead = new ListNode(0);ListNode odd = oddHead;ListNode even = evenHead;ListNode cur = head;boolean isOdd = true;while(cur != null) {if(isOdd) {odd.next = cur;odd = odd.next;}else {even.next = cur;even = even.next;}cur = cur.next;isOdd = !isOdd;}//断开原链表的链接odd.next = null;even.next = null;heads.add(oddHead.next);heads.add(evenHead.next);return heads;}public ListNode reverse(ListNode head) {ListNode prev = null;while(head != null) {ListNode next = head.next;head.next = prev;prev = head;head = next;}return prev;}public ListNode mergeTwoSortedLists(ListNode l1, ListNode l2)  {ListNode dummy = new ListNode (0);ListNode cur = dummy;while(l1 != null && l2 != null) {if(l1.val <= l2.val) {cur.next = l1;l1 = l1.next;}else {cur.next = l2;l2 = l2.next;}cur = cur.next;}//链接剩余部分if(l1 != null) {cur.next = l1;}if(l2 != null) {cur.next = l2;}return dummy.next;}