删除链表中等于给定值 val 的所有节点

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode removeElements(ListNode head, int val) {if (head == null) {return head;}ListNode prev = head;ListNode cur = head.next;while (cur != null) {if (cur.val == val) {prev.next = cur.next;} else {prev = cur;}cur = cur.next;}if (head.val == val) {head = head.next;}return head;}
}

反转一个单链表

采用头插法即可，请看vcr 

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {if (head == null)return head;ListNode cur = head.next;head.next = null;while (cur != null) {ListNode curN = cur.next;//开始反转cur.next = head;head = cur;cur = curN;}return head;}
}

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点

快慢指针：

偶数长：fast==null                             奇数长：fast.next==null

数学问题：

路程一样的情况下，速度是2倍，那么当走完的时候，路程也是两倍。

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode middleNode(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}return slow;}
}

输入一个链表，输出该链表中倒数第k个结点

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/
class Solution {public int kthToLast(ListNode head, int k) {ListNode fast = head;ListNode slow = head;// 1.先让fast走k-1步for (int i = 0; i <= k - 1; i++) {fast = fast.next;}// 2.然后一起走，当fast走到最后一个节点的时候，slow的位置就是倒数第k个节点while (fast != null) {fast = fast.next;slow = slow.next;}return slow.val;}
}

难度升级：如果k不合法，该怎么写？

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/
class Solution {public int kthToLast(ListNode head, int k) {if (k <= 0) {return -1;}ListNode fast = head;ListNode slow = head;// 1.先让fast走k-1步for (int i = 0; i <= k - 1; i++) {if (fast == null) {return -1;}fast = fast.next;}// 2.然后一起走，当fast走到最后一个节点的时候，slow的位置就是倒数第k个节点while (fast != null) {fast = fast.next;slow = slow.next;}return slow.val;}
}

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

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode headA, ListNode headB) {ListNode newH = new ListNode();ListNode temp = new ListNode();newH = temp;while (headA != null && headB != null) {if (headA.val < headB.val) {temp.next = headA;headA = headA.next;temp = temp.next;} else {temp.next = headB;headB = headB.next;temp = temp.next;}}if (headA == null)temp.next = headB;elsetemp.next = headA;return newH.next;}
}

编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前

1.遍历链表

2.把对应的节点放到指定区间

3.把两个区间连起来

import java.util.*;/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Partition {public ListNode partition(ListNode pHead, int x) {if (pHead == null) {return null;}ListNode bs = null, be = null, as = null, ae = null;ListNode cur = pHead;while (cur != null) {if (cur.val < x) {if (bs == null) {//第一次插入bs = be = cur;} else {cur.next = be;be = be.next;}} else {//第一次插入if (as == null) {as = ae = cur;} else {cur.next = ae;ae = ae.next;}}cur = cur.next;}//进行拼接be.next = as;return be;}
}

此代码存在的问题：

1.最后一个节点没有了null

2.全部小于x 全部大于x

import java.util.*;/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Partition {public ListNode partition(ListNode pHead, int x) {if (pHead == null) {return null;}// write code hereListNode bs = null;ListNode be = null;ListNode as = null;ListNode ae = null;ListNode cur = pHead;while (cur != null) {if (cur.val < x) {//第一次插入if (bs == null) {bs = be = cur;} else {be.next = cur;be = be.next;}cur = cur.next;} else {if (as == null) {//第一次插入as = ae = cur;} else {ae.next = cur;ae = ae.next;}cur = cur.next;}}//第一部分是不是空的，如果空 返回第二部分，如果不为空 进行拼接if (bs == null) {return as;}//进行拼接be.next = as;//后半部分不为空 把后半部分 最后一个节点置空if (as != null) {ae.next = null;}return bs;}
}

链表的回文结构

但是偶数节点，head和slow没办法相遇

import java.util.*;/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class PalindromeList {public boolean chkPalindrome(ListNode head) {if (head == null) {return true;}//1.遍历链表ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}//2.翻转中间节点后面的链表ListNode cur = slow.next;while (cur != null) {ListNode curN = cur.next;cur.next = slow;slow = cur;cur = curN;}//3.slow从后往前，head从前往后，直到他俩相遇while (head != slow) {if (head.val != slow.val) {return false;}if (head.next == slow) {return true;}head = head.next;slow = slow.next;}return true;}
}

输入两个链表，找出它们的第一个公共结点

/*** 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) {// 1.假设A链表长ListNode pl = headA;ListNode ps = headB;int lenA = 0;int lenB = 0;while (pl != null) {lenA++;pl = pl.next;}while (ps != null) {lenB++;ps = ps.next;}// 要重新赋值pl = headA;ps = headB;int len = lenA - lenB;// 2.判断len是正数还是负数if (len < 0) {pl = headB;ps = headA;len = lenB - lenA;}// 上述两步走完之后// pl一定指向最长的链表，ps一定指向最短的链表// len 一定是整数// 3.让长链表pl走差值len步while (len != 0) {pl = pl.next;len--;}// 一起走 直到相遇while (pl != ps) {pl = pl.next;ps = ps.next;}if (pl == null) {// 如果两个引用都为空 证明不相交 虽然不写也没问题return null;}return pl;}
}

给定一个链表，判断链表中是否有环

快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。

/*** 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) {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;}
}

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL

/*** 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) {fast = fast.next.next;slow = slow.next;if (fast == slow) {break;}}if (fast == null || fast.next == null) {return null;}fast = head;while (fast != slow) {fast = fast.next;slow = slow.next;}return fast;}
}