数据结构：LinkedList类和链表

题目描述：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

        （1）如若链表头节点为空，则返回空即可。
        （2）如若链表头节点的下一个节点为空，则说明该链表只有一个节点且为头节点，那么直接返回这个节点即可。
        （3）将头节点的next指向null。
        （4）使用前中后指针（三指针法）来将后节点（中指针）的next指向前节点（后指针），再将后指针变为中指针、中指针变为前指针、前指针变为前指针的下一个节点（next），循环此操作……直到中间指针为空停止，此时链表就被反转过来了，返回后指针即可。

class Solution {public ListNode reverseList(ListNode head) {if(head==null){return null;}if(head.next==null){return head;}ListNode cur=head.next;head.next=null;while(cur!=null){ListNode curNext=cur.next;cur.next=head;head=cur;cur=curNext;}return head;}
}

题目描述：给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

        （1）如若链表头节点为空，则返回空即可。
        （2）使用前后指针即可。前指针每次前进两次，后指针每次前进一次，直到前指针为空时，返回后指针节点即是链表的中间节点。

class Solution {public ListNode middleNode(ListNode head) {if(head==null){return null;}ListNode slow=head;ListNode fast=head;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;}return slow;}
}

题目描述：输入一个链表，输出该链表中倒数第k个结点。

        （1）如若k小于等于0，则返回空，因为倒数是没有负数的。
        （2）如若链表头节点为空，则返回空即可。
        （3）使用前后指针，让前指针先走k-1个单位，之后再前后指针一起走，直到前指针为空，后指针指向的节点就是倒数第k个节点。

public class Solution {public ListNode FindKthToTail(ListNode head,int k) {if(k<=0){return null;}if(head==null){return null;}ListNode slow=head;ListNode fast=head;while(k-1>0){fast=fast.next;if(fast==null){return null;}k--;}while(fast.next!=null){fast=fast.next;slow=slow.next;}return slow;}
}

题目描述：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

本题有多种常规的思路可以解决，这里使用其中一种：
        （1）建立一个新的链表，然后分别遍历两个升序的链表，比较两个链表中节点val值的大小，将小的加入到新建的链表当中去，直到这两个链表中有一个遍历完。
        （2）看谁遍历完，然后直接将没有遍历完的那个链表剩余的节点添加到新建的链表后面即可。

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode head=new ListNode();ListNode cur=head;while(list1!=null&&list2!=null){if(list1.val<=list2.val){cur.next=list1;list1=list1.next;}else{cur.next=list2;list2=list2.next;}cur=cur.next;}if(list1==null){cur.next=list2;}else if(list2==null){cur.next=list1;}return head.next;}
}

题目描述：现有一链表的头指针 ListNode* head，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

        （1）如若链表头节点为空，则返回空即可。
        （2）由于需要对链表进行分割，所以比较容易想到的方法是定义四个新的链表节点，将来分别用来存链表头节点、小于分割值最后节点、大于等于分割值最前节点、链表尾节点。
        （3）遍历整个链表，将小于分割值的节点串在新建的链表头节点和小于分割值最后节点之间；将大于等于分割值的节点串在新建的大于等于分割值最前节点和链表尾节点之间。
        （4）如若新建的链表头节点和小于分割值最后节点之间并没有节点存在，那么直接返回新建的大于等于分割值最前节点和链表尾节点之间的节点即可（就算这部分为空也没事，直接返回的是null）；否则，将小于分割值最后节点的next指向大于等于分割值最前节点，然后返回链表头节点即可。

public class Partition {public ListNode partition(ListNode head, int x) {// write code hereif(head==null){return null;}ListNode bs=null;ListNode be=null;ListNode as=null;ListNode ae=null;ListNode cur=head;while(cur!=null){if(cur.val<x){if(bs==null){bs=cur;be=cur;}else{be.next=cur;be=cur;}}else{if(as==null){as=cur;ae=cur;}else{ae.next=cur;ae=cur;}}cur=cur.next;}if(bs==null){return as;}be.next=as;if(as!=null){ae.next=null;}return bs;}
}

题目描述：对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。

        （1）如若链表头节点为空，则可以直接判断为不是回文链表。
        （2）如若链表头节点的下一个节点为空，则说明该链表只有一个节点且为头节点，那么不管是如何看起，都是一样的，所以可直接判断为是回文链表。
        （3）找到链表的中间节点。与上面思路一样，通过前后指针，前指针一次走两个单位，后指针一次走一个单位，直到前指针为空，后指针指向的节点就是链表的中间节点。
        （4）对中间节点后的链表进行反转。与前面链表反转操作一样，将链表中间节点视为头节点，其他操作基本都是一样。
        （5）从头尾指针分别往中间进行查找。如若头尾指针对应节点的val值是不一样的，那么直接判断其不是回文链表；如若头指针指向节点的下一个节点是尾指针指向的节点，那么可以直接判断其是回文链表；直到头尾指针相遇，则可以判断其是回文链表。

public class PalindromeList {public boolean chkPalindrome(ListNode head) {// write code hereif(head==null){return false;}if(head.next==null){return true;}//第一步：先找到中间节点ListNode slow=head;ListNode fast=head;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;}//第二步：对后半部分进行反转ListNode cur=slow.next;while(cur!=null){ListNode curNext=cur.next;cur.next=slow;slow=cur;cur=curNext;}//从前后往中间进行查找while(head!=slow){if(head.val!=slow.val){return false;}if(head.next==slow){return true;}head=head.next;slow=slow.next;}return true;}
}

题目描述：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

        （1）如若有一个链表为空，则直接返回空即可，因为他们并没有公共的交点。
        （2）遍历两个链表，分别得出两链表的长度，然后将较长的链表向前走两链表差个单位。
        （3）将两链表每次一起前进1个单位，直到两链表对应的节点相同，这个节点就是链表相交的节点。

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if(headA==null||headB==null){return null;}int lenA=0;int lenB=0;ListNode pl=headA;ListNode ps=headB;while(pl!=null){lenA++;pl=pl.next;}while(ps!=null){lenB++;ps=ps.next;}pl=headA;ps=headB;int len=lenA-lenB;if(len<0){pl=headB;ps=headA;len=-len;}while(len>0){pl=pl.next;len--;}while(pl!=ps){pl=pl.next;ps=ps.next;}return pl;}
}

题目描述：给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。

        （1）如若链表头节点为空，则判断这个链表不是环形链表。
        （2）先使用快慢指针（前后指针），前指针每次前进两个单位，后指针每次前进一个单位，如果两个指针有指向共同的节点，那么这个链表就是环形链表；否则不是环形链表。

public class Solution {public boolean hasCycle(ListNode head) {if(head==null){return false;}ListNode fast=head;ListNode slow=head;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;if(fast==slow){return true;}}return false;}
}

环形链表拓展：查找进入环形链表的节点

题目描述：判断链表是否是环形链表，如若是，则返回进入环形链表的节点。

        （1）如若链表头节点为空，则直接返回null。
        （2）与上面判断环形链表类似的，先找出前后指针相交的节点。
        （3）让后指针指回链表头节点，让前后指针每次都一起往前走一步，直到两指针相遇，则相遇的这个节点就是进入链表的节点。（下面画个图解释一下原因）

    /*** 查找进入环的节点* @return*/public ListNode detectCycle(){if(this.head==null){return null;}ListNode slow=this.head;ListNode fast=this.head;while(fast!=null && fast.next!=null){slow=slow.next;fast=fast.next.next;if(fast==slow){break;}}if(fast==null || fast.next==null){return null;}slow=this.head;while(slow!=fast){slow=slow.next;fast=fast.next;}return slow;}