1.链表分割
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
题解 ：
思路：
1.先读题，题中给一个x值，我们需要将链表通过给的值，左右分别放入小于x的数，和大于x的数。
2.可以这样操作，new两个链表，一个链表放入小于x的数，一个链表放入大于x的数，最后将两个链表进行链接。
3.链接细节：若 左表为nul，那么我们直接返回右边的头；若左边不为空，我们只需将右表的头，通过尾插法插入到左表的尾。在此之前，我们还需要判断右边的尾节点的nxet是否为空，不为空，我们需要手动制空。不然和出来的链表会带环。
import java.util.*; public class Partition { public ListNode partition(ListNode pHead, int x) { // write code here ListNode cur=pHead; //左边 ListNode leftHead=null; ListNode left=null; //右边 ListNode rightHead=null; ListNode right=null; //判断存左还是存右 while(cur!=null) { if(cur.val<x) { if(left==null) { left=cur; leftHead=cur; }else { left.next=cur; left=left.next; } }else { if(right==null) { right=cur; rightHead=cur; }else { right.next=cur; right=right.next; } } cur=cur.next; } //判断左是否为空 if(leftHead==null) { return rightHead; } //连接两个链表 left.next=rightHead; //判断右边尾结点next是否为空（若不是空，又没进行手动改空，链表会有环） if(right!=null) { right.next=null; } return leftHead; } }
2.相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题解 ：
思路：
- 1.判断两个链表是否有空链表，如果有一个是空，就不会有交点。
- 2.计算两个链表的长度，让长度长的链表走完他两个的差值。
3.再让curA和curB一起走，直到两个相等。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { //两个链表任意一个为空，都不会有交点 if(headA==null || headB==null) { return null; } //计算两个链表的长度 int lenA=0; int lenB=0; ListNode curA=headA; ListNode curB=headB; while(curA!=null) { lenA++; curA=curA.next; } while(curB!=null) { lenB++; curB=curB.next; } curA=headA; curB=headB; int diff=0; //谁长让谁把长出来的先走完 if(lenA>lenB) { diff=lenA-lenB; while(diff!=0) { diff--; curA=curA.next; } }else { diff=lenB-lenA; while(diff!=0) { diff--; curB=curB.next; } } //走完，让他们两个一起走，当两个节点地址相同时，就相遇了 while(curA!=null) { if(curA==curB) { return curA; } curA=curA.next; curB=curB.next; } return null; } }
3.环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
题解 ：
思路：
1.双指针思想
2.一个快指针，一个慢指针。慢指针走一步，快指针走两步，如若有环，快指针总能最上慢指针。
拓展：
为什么不能让快指针走三步？
答：如果走三步的话，可能套圈，也就是无法相遇。他不像我们再生活中跑步，我们相遇总是能看见，他们是无法看到对方的。
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { if(head==null||head.next==null) { return false; } //快慢指针 //快指针走两步 //慢指针走一步 ListNode fast=head.next; ListNode slow=head; while(slow!=null&&fast!=null&&fast.next!=null) { if(slow==fast) { return true; } slow=slow.next; fast=fast.next.next; } return false; } }
4.环形链表 II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
题解 ：
思路：
1.先找到相遇点。
2.找到相遇点，将fast返回到head。
3.再一步一步走，下次相遇就是入口点。
/** * 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) { ListNode fast=head; ListNode slow=head; while(fast!=null && fast.next!=null) { slow=slow.next; fast=fast.next.next; if(slow==fast) { break; } } if(fast==null||fast.next==null) { return null; } slow=head; while(slow!=fast) { slow=slow.next; fast=fast.next; } return fast; } }
