/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        //设置指针pre head next, 链表第一个节点pre就是反转之后的链表最后一个节点，所以要将pre.next设置为null
        ListNode pre = head;
        head = head.next;  
        pre.next = null; 

        ListNode next;
        //对当前节点“head”进行操作
        while(head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head == null || k<=0)
            return null;
        
        //首先遍历链表得到链表长度
        int len = lenList(head);

        if(k>len)
            return null;

        //利用前后指针，一个指针先走k个节点，另一个指针再开始走
        ListNode pHead = head, tHead = head;
        int dis = 0;
        while(dis < k){
            tHead = tHead.next;
            dis++;
        }
        while(tHead != null){
            pHead = pHead.next;
            tHead = tHead.next;
        }
        return pHead;
    }
    public int lenList(ListNode head){
        int len = 1;
        while(head.next != null){
            head = head.next;
            len++;           
        }
            
        return len;
    }
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null)
            return null;
        //首先判断这个链表中到底有没有环
        ListNode head1 = head; 
        ListNode loopnode = loopNodes(head1);
        if(loopnode == null)
            return null;
        //有环的话就要计算环中节点的个数
        ListNode loopnode2 = loopnode.next;
        int loopnode_num = 1;
        while(loopnode != loopnode2){
            loopnode2 = loopnode2.next;
            loopnode_num++;
        }
        //再次利用快慢指针计算入口节点
        ListNode pHead = head, tHead = head;
        int k = 0;
        while(k < loopnode_num){
            tHead = tHead.next;
            k++;
        }
        while(pHead != tHead){
            pHead = pHead.next;
            tHead = tHead.next;
        }
        return pHead;
    }
    public ListNode loopNodes(ListNode head){
        //使用快慢指针进行判断
        ListNode pHead = head, tHead = head;
        while(tHead.next != null && tHead.next.next!=null){
            pHead = pHead.next;
            tHead = tHead.next.next;
            if(tHead == pHead)
                return pHead;
        }
        return null;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null)
            return l2;
        if(l2 == null)
            return l1;
        //设定合并后的链表的头结点指针为head
        ListNode head,l;
        if(l1.val<l2.val){
            head = l1;
            l1 = l1.next;
        }
        else{
            head = l2;
            l2 = l2.next;
        }
        l = head;
        //当l1、l2都不为空时，通过比较大小来确定l所连接的下一个节点
        while(l1 != null && l2 != null){
            if(l1.val<l2.val){
                l.next = l1;
                l = l.next;
                l1 = l1.next;
            }
            else{
                l.next = l2;
                l = l.next;
                l2 = l2.next;
            }
        }

        //当有一个链表为空时，l就直接连接上不为空的那个链表就可以了
        if(l1 != null)
            l.next = l1;
        if(l2 != null)
            l.next = l2;
        return head;
    }
}