题目：
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1
输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]
提示：
- 列表中的节点数目在范围
[0, 104] 内 1 <= Node.val <= 500 <= val <= 50
思路：
定义一个两个节点，一个是要删除节点的前驱，一个是要删除的节点，删除的节点的前驱为头节点，要删除的节点为头节点的下一个节点，利用循环遍历，如果不等于要删除的值，就继续往回走，如果等于，就删除，最后判断头结点的值是不是要删除的节点，如果是，头结点就指向头结点的下一个节点。
代码：
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head==null){
return null;
}
ListNode prev=head;
ListNode cur=head.next;
while(cur!=null){
if(cur.val==val){
prev.next=cur.next;
cur=cur.next;
}else {
prev=cur;
cur=cur.next;
}
}
if(head.val==val){
head=head.next;
}
return head;
}
}
题目：
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
提示：
- 链表中节点的数目范围是
[0, 5000] -5000 <= Node.val <= 5000
思路：先判空，在判断头结点的下一个节点是否为空，如果是，结果就直接等于头节点，如果不为空，则进行头插，先得把头的下一个置为空，利用循环，先保存要插入的节点的下一个节点，然后进形循环头插，当遍历完链表节点为空时结束，返回头结点。
代码：
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null){
return null;
}
if(head.next==null){
return head;
}
//cur从第二个节点开始
ListNode cur=head.next;
//第一个节点next置为空
head.next=null;
while(cur!=null){
ListNode curNext=cur.next;
cur.next=head;
head=cur;
cur=curNext;
}
return head;
}
}
题目：
给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。
示例 2：
输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。
提示：
- 链表的结点数范围是
[1, 100] 1 <= Node.val <= 100
思路：找中间节点利用快慢指针问题，两者都从头结点开始走，快指针一次走2步，慢指针一次走1步，当快指针走到最后一个为空时（奇数）块指针走到最后一个的下一个为空时（偶数）循环结束。因为快指针是慢指针的2倍，所以中间节点就是慢指针最后走到的节点值。
代码：
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个结点。
思路：判断K节点是否合法，并且判断头结点是否为空，定义快慢指针，让快指针走K-1步，并判断快指针是否为空，然后让快慢指针同时走，返回慢指针。
代码：
public ListNode FindKthToTail(int k) {
if(k<=0||head==null){
return null;
}
ListNode fast=head;
ListNode slow=head;
for (int i = 0; i < k-1; i++) {
fast=fast.next;
if (fast==null){
return null;
}
}
while (fast.next!=null){
fast=fast.next;
slow=slow.next;
}
return slow;
}
结果：
题目：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
提示：
- 两个链表的节点数目范围是
[0, 50] -100 <= Node.val <= 100l1 和 l2 均按 非递减顺序 排列
思路：定义一个新链表和一个头结点，然后比较两个链表的值，谁小谁插入到新链表，然后新链表的值指向插入的结点的结点依次循环，最后谁的链表不为空，把谁插入到新链表的后面，返回新链表头结点的下一个值。
代码：
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode newHead=new ListNode();//不具备有效数据
ListNode TmpHead=newHead;
while(list1!=null&&list2!=null){
if(list1.val<list2.val){
TmpHead.next=list1;
list1=list1.next;
}else{
TmpHead.next=list2;
list2=list2.next;
}
TmpHead=TmpHead.next;
}
if(list1!=null){
TmpHead.next=list1;
}
if(list2!=null){
TmpHead.next=list2;
}
return newHead.next;
}
}
题目：
描述
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
思路：定义四个节点，x之前的开始和节数和x之后的开始和结束两段，定义循环链表值小于X，判断x之前的先判开始是否为空，开始=结束=头结点,不为空时，结束的下一个节点等于头结点，结束的等于结束的下一个节点，如果大于则进入大于x之后的结点，与上文写法一样，节点循环往下走，最后判断当第一段没有数据时，直接返回第二段的开始，否则，则把第一段和第二段连起来，让第一段结束的下一个节点等于第二段开始的结点，然后把第二段的最后一个节点置为空，返回第一段的开始的结点。
代码：
public class Partition {
public ListNode partition(ListNode pHead, int x) {
// write code here
ListNode 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;
}
}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;
}
}
题目：
描述
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
测试样例：
1->2->2->1返回：true
思路：1.先用快慢指针找出中心点，2，翻转链表，3.比较头结点和慢指针的大小，奇数链表比较是否相等，偶数链表比较头结点的下一个链表和慢指针的值是否相等。
代码：
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) {
// write code here
//找到中间节点
ListNode fast=head;
ListNode slow=head;
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
}
//翻转链表
ListNode cur=slow.next;
while(cur!=null){
ListNode curNext=cur.next;
cur.next=slow;
slow=cur;
cur=curNext;
}
//3.翻转完成，判断是否回文
while(head!=slow){
if(head.val!=slow.val){
return false;
}
if(head.next==slow){
return true;
}
head=head.next;
slow=slow.next;
}
return true;
}
}
