最近一口气刷完了Leetcode上链表专栏下的所有题。有好几题非常有意思，记录一下：

感觉链表的题，大部分都是考察细心的题。你定义好的遍历指针，一定要细心的检查当它遍历时，它的子节点正确赋值，同时要非常注意链表指针非空的情况。

寻找链表的倒数第K个，或者类似的题目。类似的比如：输出链表的后一半。

​ 要求：时间复杂度限制O(n), 空间复杂度是O(1) 解题思路：开辟两个指针p,q. 开始时俩个指针都指向头结点。然后p往后走，q不走。当P走了k步时，q再走。当p走到链表末尾事，q就是倒数第k个了。 代码：

class Solution {
    public ListNode middleNode(ListNode head,int k) {
        int i=0;
		ListNode p,q;
		p = head;
		q = head;
		while(i<k){
			if(p!=null){
				p = p.next;
				i++;
			}else{
				return null;
			}
		}
		while(p!=null){
			p = p.next;
			q = q.next;
		}
		return q;
    }
}

判断链表是否是回文链表

（回文链表：链表的值从左往右，从右往左都是一样的） 要求：时间复杂度O(n) ,空间O(1) 解题思路： 首先找到链表的中间，将链表从中间分为俩个链表。 然后反转俩个链表中的一个。最后进行依次对比。

判断链表是否有环，以及输出环的入口

判断有环解题思路：p,q两个指针指向头结点。然后p每次往前走一步，q走俩步，如果再次相遇则有环。

输出环入口解题思路：先运行判断有环的程序。这时，p,q相遇在环中的某个结点。这个结点不一定是入口。 接下来 p=相遇结点，q= 头结点。然后他们每次都走一步，再次相遇就是环入口结点。 具体证明参考：https://blog.csdn.net/xyzxiaoxiong/article/details/78761940 PS：我当时采取的是一个很暴力的方法。因为没有规定空间复杂度，所以我直接 开辟了一个HashSet的数组。每次遍历时，将当前节点加入hashSet中，第一个出现重复的元素即 是环入口。

给链表排序

题目：用O(N*logN)的时间复杂度给链表排序 解题思路：先将链表分为左右俩部分，形成俩个链表。然后对这俩个链表使用归并排序。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        ListNode slow,fast,head1,head2;
        if(head==null || head.next==null) return head;
        slow = head;
        fast = slow;
        while(fast!=null && fast.next!=null && fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        fast = slow;
        slow = slow.next;
        fast.next = null;
        head1 = sortList(head);
        head2 = sortList(slow);
        head = MergeSort(head1,head2);
        return head;
    }
    
    public ListNode MergeSort(ListNode head1,ListNode head2) {
        if(head1==null) return head2;
        if(head2==null) return head1;
        
        ListNode head,p,q,cur;
        if(head1.val < head2.val){
            head = head1;
            head1 = head1.next;
        }else{
            head = head2;
            head2 = head2.next;
        }
        p = head1;
        q = head2;
        cur = head;
        while(p!=null && q!=null){
            if(p.val<q.val){
                cur.next = p;
                cur = cur.next;
                p = p.next;
            }else{
                cur.next = q;
                cur = cur.next;
                q = q.next;
            }
        }
        while(p!=null){
            cur.next = p;
            cur = cur.next;
            p = p.next;
        }
        while(q!=null){
            cur.next = q;
            cur = cur.next;
            q = q.next;
        }
        return head;
    }
    
}

待添加。。。