1.

思路：

创建两个链表，一个用来记录小于x的结点，一个用来记录大于等于x的结点，然后遍历完原链表后，将小于x的链表和大于等于x的链表进行拼接即可

public class Partition {  public ListNode partition(ListNode pHead, int x) {  if (pHead == null || pHead.next == null) {  //如果链表为空或者只有一个结点return pHead;  }  ListNode beforeHead = new ListNode(0); // 哑节点，用于小于x的链表  ListNode before = beforeHead;  ListNode afterHead = new ListNode(0); // 哑节点，用于大于等于x的链表  ListNode after = afterHead;  while (pHead != null) {  if (pHead.val < x) {  before.next = pHead;  before = before.next;  } else {  after.next = pHead;  after = after.next;  }  pHead = pHead.next;  }  // 断开大于等于x的链表的尾部  after.next = null;  // 将小于x的链表连接到大于等于x的链表之前  before.next = afterHead.next;  return beforeHead.next;  }  
}

2.

思路：

首先要判断回文，必须要先找到中间结点，然后以中间结点为分界线，进行左右两部分判断，所以可以采用快慢指针找中间结点

因为是单向链表，右边这一部分很难从后往前走判断是否回文，所以我们要解决这个问题，可以想到的办法就是反转链表，将后面的结点的next指向它的前一个结点，相当于将中间结点后面的单向链表变成双向链表，同时慢指针走到最后一个结点

最后头结点往后走，慢指针往前走（只能用慢指针，因为当结点个数为偶数时，快指针会指向null）进行判断是否回文

public class PalindromeList {public boolean chkPalindrome(ListNode A) {// write code here//第一步：找到中间结点ListNode slow = A;ListNode fast = A;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}//第二步：反转中间结点后面的链表ListNode cur = slow.next;ListNode curN = cur.next;while (cur != null) {curN = cur.next;cur.next = slow;slow = cur;cur = curN;}//第三步：判读回文while (slow != A) {//当还没有相遇时if(A.next==slow&&A.val==slow.val){//偶数个结点回文判断结束条件return true;}if (slow.val != A.val) {//不是回文return false;}else{//继续判断slow=slow.next;A=A.next;}}return true;//奇数个结点回文判断结束条件}
}

3.

思路：

法一：一个链表作为参照，一个链表用来遍历，如果参照链表的这个结点经过另外那个链表遍历后没有发现相交，参照链表的结点往后，另外那个链表继续遍历，如此类推

法二：如果相交，那么相交之后的链表长度是相同的，所以两个链表长度的差值就等于相交前面的链表长度差值，因此只需要求出两个链表的长度，相减得出差值，让较长的链表先走差值步，然后再以相同的速度往后走，则相等时相交

代码（法一）：

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode a=headA;ListNode b=headB;while(a!=null){//每次遍历一个a链表的结点while(b!=null){//遍历全部b链表的结点if(b==a){//如果相交return b;}else{b=b.next;//继续找}}b=headB;//从头开始a=a.next;//找下一个结点}return null;//没有相交}
}

代码（法二）：

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode a=headA;ListNode b=headB;int len1=0;//a链表的长度int len2=0;//b链表的长度int len=0;//差值while(a!=null){//求a链表的长度len1++;a=a.next;}while(b!=null){//求b链表的长度len2++;b=b.next;}if(len1>len2){//如果是a链表更长len=len1-len2;a=headA;//a指向更长的那条链表b=headB;//b指向更短的那条链表}else{//如果是b链表更长len=len2-len1;a=headB;//a指向更长的那条链表b=headA;//b指向更短的那条链表}while(len!=0){//让长链表先走差值步len--;a=a.next;}while(a!=b){//如果还没有相交a=a.next;b=b.next;}if(a==null){//没有相交return null;}return a;//相交点}
}

4.

思路：

如果没有环的话，那么一定会有一个尽头，即一定会走到null，如果有环的话，那么将永远没有尽头，即不存在null，这个环可以看作是一个圆形操场，就变为简单的追及相遇这个数学问题，所以需要快慢指针，如果有环，那么快指针一定和慢指针相遇

public class Solution {public boolean hasCycle(ListNode head) {if(head==null){//如果是空链表return false;}ListNode slow=head;ListNode fast=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 false;//没有环}return true;//如果是因为相遇而跳出的循环，则有环}
}

5.

思路：

首先判断是否有环，跟上面一题一样，接下来，如果有环，求出环的开始结点，还是快慢指针，快指针一次走两步，慢指针一次走一步，用两个公式表示快慢指针走的路程，其中C是环的长度，K是相遇点距离环的开始结点的长度，X表示头结点到环的开始结点的长度

1.fast走的路程S1：X+NC+C-K

2.slow走的路程S2：X+C-K

并且S1=2S2

所以

X+NC+C-K=2*(X+C-K)

X+NC+C-K=2X+2C-2K

X=(N-1)C+K

由该公式可得，从头结点到环的开始结点等于从相遇点走N-1圈再走到环的开始结点，所以让slow从头结点开始，fast从相遇点开始，以相同的速度开始走，那么再次相遇的位置就是环的开始结点

public class Solution {public ListNode detectCycle(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;if(slow==fast){//如果相遇break;}}if(fast==null||fast.next==null){//如果是因为走到尽头，则无环return null;}//因为相遇，则有环slow=head;//从头走到环的开始结点while(slow!=fast){//走到相遇slow=slow.next;fast=fast.next;}return slow;//返回相遇点（即环的开始结点)}
}

6.

思路：

首先先判断特殊情况：两个链表都为空，或者其中一个链表为空，则返回null

然后是正常情况，因为两个链表都是升序的，所以先比较两个链表的头结点，较小的那个结点则一定为两个链表中最小的，所以该结点为合并后新的头结点，然后用一个指针cur去接收两个链表较小的结点，尾插在新的头结点后面，如此类推

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode newH=null;//合并后的头结点if(list1==null&&list2==null){//两个链表都为空return null;}if(list1==null){//其中一个链表为空return list2;}if(list2==null){//另外一个链表为空return list1;}ListNode a=list1;ListNode b=list2;if(a.val<b.val){newH=a;//说明合并后的新头结点为a链表的头结点a=a.next;}else{newH=b;//说明合并后的新头结点为b链表的头结点b=b.next;}ListNode cur=newH;//用来遍历链表while(a!=null&&b!=null){//当两个链表都没有走完if(a.val<b.val){//a的小于b，则插acur.next=a;cur=cur.next;a=a.next;}else{//a的大于等于b，则插bcur.next=b;cur=cur.next;b=b.next;}}while(a!=null){//当b链表走完而a链表没有走完，将a链表全部尾插cur.next=a;cur=cur.next;a=a.next;}while(b!=null){//当a链表走完而b链表没有走完，将b链表全部尾插cur.next=b;cur=cur.next;b=b.next;}return newH;//返回合并后的新头结点}
}