Leetcode328奇偶链表，Leetcode21合并两个有序链表，Leetcode206反转链表 三者综合题
题目描述
思路分析
这题的思路就和我们的标题所述一样，可以看作是这3个题的合并，但是稍微还有一点点区别
比如：奇偶链表这道题主要是偶数链在了奇数后面，字节这个的话是奇偶链表分离了
所以字节这题的大概思路就是：
将奇偶链表分离，反转偶链表，然后将反转后的偶链表和奇链表进行合并（也就是合并两个有序链表）
总体来说不是很难，思路也比较清晰，还是比较好实现的
不得不说大厂的题还是考的全面，一个题考了3个知识点
代码实现
public ListNode sortLinkedList(ListNode head) {
if(head == null || head.next == null) {
return head;
}
// 分离链表为单索引和双索引两个子链表, 并返回链表的头节点，0 - oddHead, 1 - evenHead
List<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;
}总结
如果大家对其中的某一道题还不熟悉的话，建议去刷一下对应的题目，这里给了传送门
原文地址：https://blog.csdn.net/weixin_73618012/article/details/143495874
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！