算法——字符串（一）

1、两数相加

 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 }

2、删除链表倒数第k个节点

快慢指针的思想

 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 }

3、合并两个有序链表

 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 }

4、合并K个有序链表

分治的思想

 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 }

5、两两交换链表的节点

 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 }