链表算法题一

​

旋转链表

旋转链表

首先考虑特殊情况

1. 若给定链表为空表或者单个节点,则直接返回head,不需要旋转操作.
2. 题目给定条件范围:$0<=k<=2\ast 10^9$,但是受给定链表长度的限制,比如示例2中,k=4与k=1的效果等价.
   那么可以得出k=k%len的式子,其中len为数组长度.
3. 先遍历原链表,求得len.
4. 求得新链表的头节点,尾节点在原链表中位置,修改指针指向即可.

class Solution {public ListNode rotateRight(ListNode head, int k) {if(head==null||head.next==null) return head;int len = 0;//遍历求链表长度并且求出原链表的末尾节点.ListNode tail = head;while(tail.next!=null){tail = tail.next;len++;}len++;//处理kk = k % len;if(k==0) return head;//找新链表的尾节点.int n = len-k-1;ListNode cur = head;while(n>0){cur = cur.next;n--;}tail.next = head;//找到新链表的头节点,其后修改指针指向即可.head = cur.next;cur.next = null;return head;}
}

合并K个链表

分治思想+归并排序

注意此题与数组的归并排序区别.
分治部分和数组相同,但合并部分merge函数实际是此题:合并两个有序链表.
如果了解归并排序和做个上面那道题,思路一通水到渠成.
结论:链表的归并排序空间复杂度:$O(1)$

class Solution {private ListNode mergeListSort(ListNode[] lists,int start,int end){if(start>end)return null;if(start==end)return lists[start];int mid = start + (end-start)/2;ListNode left = mergeListSort(lists,start,mid);ListNode right = mergeListSort(lists,mid+1,end);return merge(left,right);}private ListNode merge(ListNode left,ListNode right){if(left==null)return right;if(right==null)return left;ListNode cur1 = left,cur2 = right;ListNode head = new ListNode();ListNode tail = head;while(cur1!=null&&cur2!=null){if(cur1.val<=cur2.val){tail.next = cur1;cur1 = cur1.next;tail = tail.next;}else{tail.next = cur2;cur2 = cur2.next;tail = tail.next;}}if(cur1!=null)tail.next=cur1;if(cur2!=null)tail.next=cur2;return head.next;} public ListNode mergeKLists(ListNode[] lists) {if(lists==null||lists.length==0)return null;//MergeSort启动!return mergeListSort(lists,0,lists.length-1);//当lists.length==1时,上式会返回lists.}
}

​力扣只写了两道题的笔记,太累了写不动ε(┬┬﹏┬┬)3.
力扣折磨.