1、两数相加
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 class Solution { 2 public ListNode addTwoNumbers(ListNode l1, ListNode l2) { 3 ListNode pre = new ListNode(); 4 ListNode cur = pre; 5 int carry = 0; 6 while(l1!=null||l2!=null||carry!=0){ 7 int x=0,y=0; 8 if(l1!=null){ 9 x=l1.val; 10 l1=l1.next; 11 } 12 if(l2!=null){ 13 y=l2.val; 14 l2=l2.next; 15 } 16 int sum=(x+y+carry)%10; 17 ListNode newnode=new ListNode(sum); 18 cur.next=newnode; 19 carry=(x+y+carry)/10; 20 cur=cur.next; 21 22 } 23 return pre.next; 24 } 25 }View Code
2、删除链表倒数第k个节点
快慢指针的思想
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 class Solution { 2 public ListNode removeNthFromEnd(ListNode head, int n) { 3 ListNode dummy=new ListNode(); 4 ListNode pre=dummy; 5 pre.next=head; 6 ListNode fast=head; 7 ListNode slow=head; 8 int i=0; 9 while(fast!=null&&i<n){ 10 fast=fast.next; 11 i++; 12 } 13 while(fast!=null){ 14 fast=fast.next; 15 pre=pre.next; 16 slow=slow.next; 17 } 18 pre.next=slow.next; 19 return dummy.next; 20 21 } 22 }View Code
3、合并两个有序链表
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 class Solution { 2 public ListNode mergeTwoLists(ListNode list1, ListNode list2) { 3 ListNode dummy=new ListNode(); 4 ListNode pre=dummy; 5 //dummy.next=pre; 6 while(list1!=null&&list2!=null){ 7 if(list1.val<=list2.val){ 8 pre.next=list1; 9 list1=list1.next; 10 pre=pre.next; 11 }else{ 12 pre.next=list2; 13 list2=list2.next; 14 pre=pre.next; 15 } 16 17 } 18 if(list1!=null)pre.next=list1; 19 if(list2!=null)pre.next=list2; 20 return dummy.next; 21 } 22 }View Code
4、合并K个有序链表
分治的思想
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 class Solution { 2 public ListNode mergeKLists(ListNode[] lists) { 3 if (lists == null || lists.length == 0) return null; 4 return merge(lists, 0, lists.length - 1); 5 } 6 7 private ListNode merge(ListNode[] lists, int left, int right) { 8 if (left == right) return lists[left]; 9 int mid = left + (right - left) / 2; 10 ListNode l1 = merge(lists, left, mid); 11 ListNode l2 = merge(lists, mid + 1, right); 12 return mergeTwoLists(l1, l2); 13 } 14 15 private ListNode mergeTwoLists(ListNode l1, ListNode l2) { 16 if (l1 == null) return l2; 17 if (l2 == null) return l1; 18 if (l1.val < l2.val) { 19 l1.next = mergeTwoLists(l1.next, l2); 20 return l1; 21 } else { 22 l2.next = mergeTwoLists(l1,l2.next); 23 return l2; 24 } 25 } 26 }View Code
5、两两交换链表的节点
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 class Solution { 2 public ListNode swapPairs(ListNode head) { 3 ListNode dummy=new ListNode(); 4 dummy.next=head; 5 ListNode pre=dummy,start=head,end=head; 6 while(start!=null&&start.next!=null){ 7 end=start.next; 8 ListNode nex=end.next; 9 pre.next=end; 10 end.next=start; 11 start.next=nex; 12 pre=start; 13 start=nex; 14 15 } 16 return dummy.next; 17 } 18 }View Code
标签:pre,ListNode,next,算法,l2,l1,字符串,null From: https://www.cnblogs.com/coooookie/p/17458693.html