网站的建设与应用精准引流推广公司
旋转链表
旋转链表
首先考虑特殊情况
- 若给定链表为空表或者单个节点,则直接返回
head,不需要旋转操作. - 题目给定条件范围: 0 < = k < = 2 ∗ 1 0 9 0 <= k <= 2 * 10^9 0<=k<=2∗109,但是受给定链表长度的限制,比如示例2中,k=4与k=1的效果等价.
那么可以得出k=k%len的式子,其中len为数组长度. - 先遍历原链表,求得
len. - 求得新链表的头节点,尾节点在原链表中位置,修改指针指向即可.
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 ) O(1) 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.
力扣折磨.