代码的鲁棒性

链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个节点。
示例1
输入：1,{1,2,3,4,5}
返回值：{5}

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

    ListNode(int val) {
        this.val = val;
    }
}*/
//利用栈的特性——先入后出
import java.util.Stack;
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null||k==0)
            return null;
        Stack<ListNode> s=new Stack<>();
        while(head!=null)
        {
            s.push(head);
            head=head.next;
        }
        if(k>s.size())
            return null;
        while(k-1!=0&&k<=s.size())
        {
            k--;
            s.pop();
        }
        return s.peek();
    }
}
//双指针
//首先定义两个指向链表头的指针p和q,先令p指针指向第k节点，然后两个指针同时向后移动，最后q指向的即为倒数第k个节点。当k为零或节点为空返回。
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null||k==0)
            return null;
        ListNode p=head;
        ListNode q=head;
        while(k-1!=0)
        {
            p=p.next;
            k--;
            if(p==null)
                return null;
        }
        while(p.next!=null)
        {
            q=q.next;
            p=p.next;
        }
        return q;
    }
}

测试用例

• 功能测试（第k个节点在链表的中间；第k个结点是链表的头节点；第k个节点是链表的尾结点）；
• 特殊用例测试（链表头节点为null；链表的节点总数少于k;k等于0）。

链表中环的入口节点
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

/*
 public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if(pHead==null||pHead.next==null)
            return null;
        ListNode p=pHead,q=pHead;
        while(q!=null)
        {
            p=p.next;
            q=q.next.next;
            if(q==null)
                return null;
            if(p==q)
                break;
        }
        p=pHead;
        while(p!=q)
        {
            p=p.next;
            q=q.next;
        }
        return q;
    }
}

测试用例

• 功能测试（链表中包含或者不包含环；链表中有多个或者只有一个节点）；
• 特殊输入测试（链表头节点为null）。

反转链表
输入一个链表，反转链表后，输出新链表的表头。
示例1
输入：{1,2,3}
返回值：{3,2,1}

//利用栈的特性
import java.util.Stack;
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head==null || head.next==null)
            return head;
        Stack<ListNode> s=new Stack<>();
        while(head.next!=null)
        {
            s.push(head);
            head=head.next;
        }
        ListNode l=head;
        while(!s.isEmpty())
        {
            head.next=s.pop();
            head=head.next;
        }
        head.next=null;
        return l;
    }
}
//三指针
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head==null || head.next==null)
            return head;
        ListNode pre=null,next=null;
        while(head!=null)
        {
            next=head.next;
            head.next=pre;
            pre=head;
            head=next;
        }
        return pre;
    }
}

测试用例

• 功能测试（输入的链表中有多个节点；只有一个节点）；
• 特殊输入测试（链表头节点为null）。

合并两个排序的链表
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
示例1
输入：{1,3,5},{2,4,6}
返回值：{1,2,3,4,5,6}

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

测试用例

• 功能测试（输入的两个链表有多个节点；节点的值互不相同或者存在值相等的多个节点）；
• 特殊输入测试（两个链表的一个或者两个头节点为null；两个链表中只有一个节点）。