反转链表
给定单链表的头节点 head ，请你反转链表，并返回反转后的链表。
思路：反转链表就是总体调整方向，这时候只需遍历一遍链表，注意，开始时，cur在head位置，prev为cur位置的前一个结点，开始时为空，首先需要设置一个保留下一个结点地址的curNext，此时cur位置的指向就可以改变成相反方向prev位置，然后cur走到curNext位置，以cur不为空进行循环，就可以达到翻转的目的
class Solution {
public ListNode reverseList(ListNode head) {
ListNode cur=head;
ListNode prev = null;
//保存下一个结点
while(cur!=null){
ListNode curNext = cur.next;
cur.next=prev;
prev=cur;
cur=curNext;
}
return prev;
}
}
链表的中间结点
给定一个头结点为 head 的非空单链表，返回链表的中间结点。 如果有两个中间结点，则返回第二个中间结点。 输入：[1,2,3,4,5] 输出：此列表中的结点 3
输入：[1,2,3,4,5,6] 输出：此列表中的结点 4
思路：找到中间结点，比较简单，运用快慢指针，快的结点一次性走两步，慢的一次性走一步，最终快指针fast到达空指针位置或者fast.next到空指针的位置，循环停止，这时候满指针flow走的距离就是快指针的一般，对应的位置就是中间结点
class Solution {
public ListNode middleNode(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast!=null&&fast.next!=null){
slow=slow.next;
fast=fast.next.next;
}
return slow;
}
}
链表的回文结构
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
测试样例：1->2->2->1 返回：true
思路：回文链表面试中比较常见，其最优解法就是运用前面两道题的思想，并结合起来，先用快慢指针的方法，找到中间的位置，再将后面的序列与之倒序,此时slow就是这个链表的尾端，通过尾端和首端，都相向移动，如果相遇，则是回文链表，如果过程中，不相等，两边的值，则不是回文链表。还需判断特殊情况，当链表长度为偶数，可以通过相邻时，某个链表的next.val是否等于当前的val；
public class PalindromeList {
public boolean chkPalindrome(ListNode A) {
//判断是否为回文链表，首先找到中间值
if(A == null)return false;
if(A.next == null)return true;
ListNode fast = A;
ListNode slow = A;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
//此时slow就是中间值，然后反转后面的结点
ListNode cur = slow;
ListNode nextNode = null;
while(cur != null){
nextNode = cur.next;
cur.next = slow;
slow = cur;
cur = nextNode;
}
while(slow != A){
if(slow.val != A.val){
return false;
}
slow=slow.next;
A = A.next;
//判断偶数
if(A.next==slow && A.val==slow.val){
return true;
}
}
return true;
}
}
合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
思路：合并两个有序列表成新的链表，则此时可以创建一个链表，通过比较合并前的两个链表的val值，判断大小，小的先放进新的链表中，最终新的链表就是完全时有序的链表。当一个链表为空时，那新的链表只需要将最后一个结点的next值与另一个链表连接起来，就完成了合并两个链表。
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode newHead = new ListNode(1);
ListNode temp = newHead;
while(list1 != null && list2 != null){
if(list1.val<list2.val){
temp.next = list1;
temp = list1;
list1 = list1.next;
}else{
temp.next = list2;
temp = list2;
list2 = list2.next;
}
}
if(list1 == null){
temp.next =list2;
}
if(list2 == null){
temp.next = list1;
}
return newHead.next;
}
}
链表中倒数第k个结点
输入一个链表，输出该链表中倒数第k个结点。
输入：{1,2,3,4,5},1
返回值：{5}
思路：这道题还是可以借助快慢指针来解决，这倒数k个结点，就相当于快的指针夺走了k-1步，如果快的真正fast.next为null，此时的slow就是慢指针的位置就是倒数第k个结点
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(k <= 0)
return null;
ListNode low = head;
ListNode fast = head;
for(int i=1; i < k;i++){
if(fast == null)
return null;
else
fast = fast.next;
}
if(fast == null)
return null;
while(fast.next != null){
low = low.next;
fast = fast.next;
}
return low;
}
}
相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5]
输出：Intersected at ‘8’
思路：两个结点相交，则后续的结点是重合的，也就是说它们公用这几个结点，这两个链表的长度只差的绝对值，就是解题的关键，这时候求出长度差后，只需要让长链表先走长度差的距离，最后两个链表同时遍历，每一次走过一个结点，相遇的结点，就是要找的相交结点。如果遍历完，两者的指向还是不相等，则不存在相交结点，此时返回空结点null。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if((headA == null) || (headB == null)) return null;
//先求出链表长度的差值
int lengthSub = length(headA)-length(headB);
if(lengthSub<0){
lengthSub=-lengthSub;
}
//假设headA链表长度要长一些
if(length(headA) > length(headB)){
for(int i=0;i<lengthSub;i++){
headA = headA.next;
}
}else{
for(int i=0;i<lengthSub;i++){
headB = headB.next;
}
}
while(headA != headB){
headA = headA.next;
headB = headB.next;
}
if(headA == headB){
return headA;
}else{
return null;
}
}
public static int length(ListNode head){
ListNode cur = head;
int length = 0;
while(cur != null){
cur = cur.next;
length++;
}
return length;
}
}
链表分割
现有一链表的头结点pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
思路：给出了分界值，大体思路只需要创建两个链表，如果给出的pHead链表上的结点val值小于x值，则放在前面一个链表，反之放在后面一个链表，最后两个链表进行拼接，就形成了一个新的链表，就是重新排序后的链表。但是最后需要将第二个链表置为空，防止形成环。
public class Partition {
public ListNode partition(ListNode Head, int x) {
if(Head==null){
return null;
}
ListNode firstStare= null;
ListNode firstEnd= null;
ListNode laterStare= null;
ListNode laterEnd= null;
ListNode cur=Head;
while(cur != null){
if(cur.val < x ){
if(firstStare == null){
firstStare = cur;
firstEnd = cur;
cur = cur.next;
}else{
firstEnd.next = cur;
firstEnd = cur;
cur = cur.next;
}
}else{
if(laterStare == null){
laterStare = cur;
laterEnd = cur;
cur = cur.next;
}else{
laterEnd.next = cur;
laterEnd = cur;
cur = cur.next;
}
}
}
if(firstStare == null){
return laterStare;
}
if(laterEnd != null){
laterEnd.next = null;
}
firstEnd.next = laterStare;
return firstStare;
}
}
环形链表
给定一个链表，判断链表中是否有环
快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表其实位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。如果相遇，就代表形成了一个环。快指针一次性可以走三步，四步吗？答案是，不能！因为可能会出现特殊情况，当慢指针走一步，快指针走三步，这时候两个指针永远也不会相遇，即使是一个环形链表。
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fast==slow){
return true;
}
}
return false;
}
}
环形链表 II
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL
思路：让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fast==slow){
fast = head;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}