目录

11.remove-duplicates-from-sorted-list

12.remove-duplicates-from-sorted-list-ii

13.merge-two-sorted-lists

14.merge-k-sorted-lists

15.sort-list

16.insertion-sort-list

17.add-two-numbers

19.copy-list-with-random-pointer

11.remove-duplicates-from-sorted-list

题目：删除给出链表中的重复元素，使链表中的所有元素都只出现一次。例如：给出的链表为1->1->2,返回1->2.给出的链表为1->1->2->3->3,返回1->2->3.

分析：找出第一个与当前结点不相等的结点即可。

   public ListNode deleteDuplicates(ListNode head) {ListNode cur = head;while(cur != null){ListNode curNext = cur.next;while(curNext != null && cur.val == curNext.val){curNext = cur.next;}cur.next = curNext;cur = curNext;}return  head;}

12.remove-duplicates-from-sorted-list-ii

题目：给出一个排好序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。例如：给出的链表为1->2->3->3->4->4->5, 返回1->2->5.给出的链表为1->1->1->2->3,  返回2->3.

分析：见剑指offer面试题18https://blog.csdn.net/Nibaby9/article/details/104050540

13.merge-two-sorted-lists

题目：将两个有序的链表合并为一个新链表，要求新的链表是通过拼接两个链表的节点来生成的。

分析：用两个指针标记原先链表的未插入的头结点，以及一个指针标记新链表的最后一个结点即可。

   public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode preHead = new ListNode(0);ListNode cur = preHead;ListNode head1 = l1,head2 = l2;while(head1 != null && head2 != null){if(head1.val <= head2.val){cur.next = head1;head1 = head1.next;}else{cur.next = head2;head2 = head2.next;}cur = cur.next;}if(head1 != null)cur.next = head1;elsecur.next = head2;return preHead.next;}

14.merge-k-sorted-lists

题目：合并k个已排序的链表并将其作为一个已排序的链表返回。分析并描述其复杂度。 

分析：采用二分归并排序算法思想即可。

    public ListNode mergeKLists(ArrayList<ListNode> lists) {if(lists.size() == 0)return null;return mergeKLists(lists,0,lists.size()-1);}private ListNode mergeKLists(ArrayList<ListNode> lists, int low, int high) {if(low == high)return lists.get(low);int mid = (low + high) / 2;ListNode head1 = mergeKLists(lists,low,mid);ListNode head2 = mergeKLists(lists,mid + 1,high);return merge(head1,head2);}private ListNode merge(ListNode head1, ListNode head2) {ListNode preHead = new ListNode(0);ListNode cur = preHead;while(head1 != null && head2 != null){if(head1.val <= head2.val){cur.next = head1;head1 = head1.next;}else{cur.next = head2;head2 = head2.next;}cur = cur.next;}if(head1 != null)cur.next = head1;if(head2 != null)cur.next = head2;return preHead.next;}

15.sort-list

题目：在O(n log n)的时间内使用常数级空间复杂度对链表进行排序。

分析：采用归并排序的思想，利用快慢指针来找出中间节点。

    public ListNode sortList(ListNode head) {if(head==null || head.next==null)return head;ListNode mid = getMid(head);ListNode midNext = mid.next;//将链表断开mid.next = null;return mergeList(sortList(head),sortList(midNext));}ListNode getMid(ListNode head){ListNode slow = head;ListNode quick = head;while(quick.next!=null && quick.next.next!=null){slow = slow.next;quick = quick.next.next;}return slow;}ListNode mergeList(ListNode head1,ListNode head2){ListNode head = new ListNode(0);ListNode cur = head,node1 = head1,node2 = head2;while(node1!=null && node2!=null){if(node1.val < node2.val){cur.next = node1;node1 = node1.next;}else{cur.next = node2;node2 = node2.next;}cur = cur.next;}if(node1!=null)cur.next = node1;else cur.next = node2;return head.next;}

16.insertion-sort-list

题目：使用插入排序对链表进行排序。

分析：按插入排序思想排序即可。

    public ListNode insertionSortList(ListNode head) {if(head==null || head.next==null){return  head;}ListNode cur = head.next;ListNode pNode = new ListNode(0);//考虑到插在第一位的情况pNode.next = head;head.next = null;//新链表！！！while(cur!=null){ListNode target = pNode;while(target!=null){if(target.next==null || target.next.val>=cur.val)break;target = target.next;}ListNode copy = cur.next;cur.next = target.next;target.next = cur;cur = copy;}return pNode.next;}

17.add-two-numbers

题目:给定两个代表非负数的链表，数字在链表中是反向存储的（链表头结点处的数字是个位数，第二个结点上的数字是百位数...），求这个两个数的和，结果也用链表表示。输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)；输出： 7 -> 0 -> 8

分析：注意计算结束后是否要加上最高位1.

   public ListNode addTwoNumbers(ListNode l1, ListNode l2) {if(l1 == null || l2 == null)return l1 == null ? l2 : l1;ListNode preHead = new ListNode(0);ListNode cur = preHead;int flag = 0;while(l1 != null && l2 != null){int count = l1.val + l2.val + flag;cur.next = new ListNode(count % 10);flag = count / 10;cur = cur.next;l1 = l1.next;l2 = l2.next;}while(l1 != null){int count = l1.val + flag;cur.next = new ListNode(count % 10);flag = count / 10;cur = cur.next;l1 = l1.next;}while(l2 != null){int count = l2.val + flag;cur.next = new ListNode(count % 10);flag = count / 10;cur = cur.next;l2 = l2.next;}if(flag == 1)cur.next = new ListNode(1);return preHead.next;}

19.copy-list-with-random-pointer

题目：现在有一个这样的链表：链表的每一个节点都附加了一个随机指针，随机指针可能指向链表中的任意一个节点或者指向空。请对这个链表进行深拷贝。

分析：见剑指offer面试题35https://blog.csdn.net/Nibaby9/article/details/104050540