2018-09-29

• 剑指offer 链表中倒数第k个结点

/*public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
    this.val = val;
}
}*/
//两个相距k的指针在平移，后面一个移到头，前面一个就是倒数第k个
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
    if(head==null||k<=0)return null;
    else {
        ListNode pre = head;
        ListNode end = head;
        for(int i = 0;i<k-1;i++){
            if(end.next==null)return null;
            else end = end.next;
        }
        while(end.next!=null){
            end = end.next;
            pre = pre.next;
        }
        return pre;
    }
  }
}

• 反转链表后，输出新表头

/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
    this.val = val;
}
}*/
//先把head的下一个结点存一下，然后将head的next指针指向前一个结点pre，将pre和head都向后移，直到表尾全部排好，pre就是表头
public class Solution {
public ListNode ReverseList(ListNode head) {
    ListNode pre =null;
    ListNode next = null;
    while(head!=null){
        next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    return pre;
}
}

• 合并两个排序的链表
  1. 非递归的方法

/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
    this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
    if(list1==null)
        return list2;
    if(list2==null)
        return list1;
    ListNode newHead = null;
    ListNode current = null;
    while(list1!=null&&list2!=null){
        if(list1.val<=list2.val){
            if(newHead==null){
                newHead = current = list1;
            }else{
                current.next = list1;
                current = current.next;
            }
            list1 = list1.next;
        }else{
            if(newHead==null){
                newHead = current = list2;
            }else{
                current.next = list2;
                current = current.next;
            }
            list2 = list2.next;
        }
    }
    if(list1 == null){
        current.next = list2;
    }else{
        current.next = list1;
    }
    return newHead;
}
}

2. 递归方法

/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
    this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
    if(list1==null)
        return list2;
    if(list2==null)
        return list1;
    if(list1.val<=list2.val){
        list1.next = Merge(list1.next,list2);
        return list1;
    }else{
        list2.next = Merge(list1,list2.next);
        return list2;
    }
}
}