前言
之前小六六一直觉得自己的算法比较菜，算是一个短板吧，以前刷题也还真是三天打鱼，两台晒网，刷几天，然后就慢慢的不坚持了，所以这次，借助平台的活动，打算慢慢的开始开刷，并且自己还会给刷的题总结下，谈谈自己的一些思考，和自己的思路等等，希望对小伙伴能有所帮助吧，也可以借此机会把自己短板补一补，希望自己能坚持下去呀
链表
- 六六力扣刷题链表之移除链表元素
- 六六力扣刷题链表之反转链表
- 六六力扣刷题链表之两两交换链表中的节点
- 六六力扣刷题链表之合并两个有序链表
- 六六力扣刷题链表之反转链表 II
- 六六力扣刷题链表之分隔链表
- 六六力扣刷题链表之环形链表
链表的理论基础
链表的种类主要为：单链表，双链表，循环链表 链表的存储方式：链表的节点在内存中是分散存储的，通过指针连在一起。 链表是如何进行增删改查的。 数组和链表在不同场景下的性能分析。 可以说把链表基础的知识都概括了，但又不像教科书那样的繁琐。
虚拟头结点
链表的一大问题就是操作当前节点必须要找前一个节点才能操作。这就造成了，头结点的尴尬，因为头结点没有前一个
题目
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
输入： head = [4,2,1,3] 输出： [1,2,3,4]
思路
看到这题，六六还是有点懵逼，第一次做这题，也没啥思路，后面看得答案，其实也就是排序，但是就是是链表的排序，看了下答案才恍然大悟
对链表自顶向下归并排序的过程如下。
- 找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
对两个子链表分别排序。
- 将两个排序后的子链表合并，得到完整的排序后的链表。可以使用 合并两个有序链表 的做法，将两个有序的子链表进行合并。
- 上述过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于 11，即当链表为空或者链表只包含 11 个节点时，不需要对链表进行拆分和排序。
class Solution { public ListNode sortList(ListNode head) { return sortList(head, null); } public ListNode sortList(ListNode head, ListNode tail) { if (head == null) { return head; } if (head.next == tail) { head.next = null; return head; } ListNode slow = head, fast = head; while (fast != tail) { slow = slow.next; fast = fast.next; if (fast != tail) { fast = fast.next; } } ListNode mid = slow; ListNode list1 = sortList(head, mid); ListNode list2 = sortList(mid, tail); ListNode sorted = merge(list1, list2); return sorted; } public ListNode merge(ListNode head1, ListNode head2) { ListNode dummyHead = new ListNode(0); ListNode temp = dummyHead, temp1 = head1, temp2 = head2; while (temp1 != null && temp2 != null) { if (temp1.val <= temp2.val) { temp.next = temp1; temp1 = temp1.next; } else { temp.next = temp2; temp2 = temp2.next; } temp = temp.next; } if (temp1 != null) { temp.next = temp1; } else if (temp2 != null) { temp.next = temp2; } return dummyHead.next; } }
其实就是归并排序的一个写法，其实最主要有以下几个部分
- 第一个就是怎么找到中心节点，也就是我们所说的快慢指针，快的走2步，慢的走一步，等快的结束，慢点就是我们的中心
- 第二就是 我们找到中心节点之后，就是用递归的方式去把第一 和中心的数据，中间数据和最后一个数据去排序递归
- 递归的条件就是假设只剩下一个节点活着开始节点和结束节点相等的时候，结束递归
结束
好了，今天的每日一题就到这里了，大家加油，有点小难，我是小六六，三天打鱼，两天晒网！
