知识点

1. 知识点

   1. 归并排序（链表的归并排序）

      利用快慢指针找到链表中点，然后排序。例如，以升序对某个链表进行归并排序的代码为：

       public void mergeSort(ListNode head, ListNode tail) { // 
           // base case。当链表为空或者只有一个节点时，返回
           if (head == null) return null;
           if (head == 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 head1 = sort(head, slow);
           ListNode head2 = sort(slow, tail);
      
           // 治
           ListNode sorted = merge(head1, head2);
      
           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;
       }

LeetCode算法题

1. LeetCode算法题

   1. 82.【删除排序链表中的重复元素 II】

      解题思路：

      链表兼具了递归和迭代结构，因此解题思路一定是递归或者迭代

      由于给定的链表是排好序的，因此重复的元素在链表中出现的位置是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。

      最需要注意的一点是，因为可能头结点和头结点.next节点也是重复的，需要删除，因此需要新建一个哑巴节点连接头结点，预防这种情况。

   2. 148.【排序链表】

      解题思路：

      首先，先考虑排序算法中所有时间复杂度为O(nlogn)的，只有：归并排序、堆排序和快速排序。因为链表具有递归结构，首先考虑归并排序。

      归并排序有两种，自顶向下和自底向上的。

      首先，自顶向下的归并排序：利用递归写法，时间复杂度O(nlogn)，空间复杂度O(logn)。排序过程如下

      1，找到链表的中点，以中点为分界，将链表拆分成两个子链表。链表找中点，使用快慢指针即可。

      2，对两个子链表分别排序

      3，合并排好序的两个链表