链表分割
思路：
- 创建两个链表（A，B）：分别创建两个头尾指针置null
- 创建一个cur的指针遍历题目所给链表
- 将结点值小于x的尾插入A中，否则插入B中
- 判断若A段为空，返回B段头结点
- 为了防止死循环，若B段存在，则有可能B段最后一个结点不为空，若不为空，则置为空
- 用A链表的尾结点，连接B链表的头结点
public class Partition {
public ListNode partition(ListNode head, int x) {
ListNode as = null;
ListNode ae = null;
ListNode bs = null;
ListNode be = null;
ListNode cur = head;
while(cur != null){
//进a段
if(cur.val < x){
//第一次进as
if(as == null){
as = cur;
ae = cur;
}
else{
ae.next = cur;
ae = cur;
}
}
else{
if(bs == null){
bs = cur;
be = cur;
}
else{
be.next = cur;
be = cur;
}
}
cur = cur.next;
}
//如果a段为空
if(as == null){
return bs;
}
//防止死循环，如果b段存在，那么有可能b段最后一个结点的不为空
if(bs != null){
be.next = null;
}
ae.next = bs;
return as;
}
}链表回文结构
思路：
- 创建快慢指针
- 通过快慢指针遍历链表
- 从慢指针的next开始反转后半段链表
- 最后用两指针，分别从头尾判断链表是否回文
public class PalindromeList {
public boolean chkPalindrome(ListNode head) {
if(head == null){
return true;
}
ListNode fast = head;
ListNode slow = head; //快慢指针注意前后顺序，否则会引起对null指针的解引用操作
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}// 1 2 2 1
//开始反转
ListNode cur = slow.next;
while(cur != null){
ListNode curNext =cur.next;
cur.next = slow;
slow = cur;
cur = curNext;
}
//判断回文
cur = head;
while(cur != slow){
if(cur.val != slow.val){
return false;
}
if(cur.next == slow){
return true;
}
cur = cur.next;
slow = slow.next;
}
return true;
}
}合并两个有序链表
思路：
- 创建一个虚拟结点
- 从头开始比较两个结点value值，将较小值连接虚拟结点
- 若有一个结点为空时，将该结点指向另一个结点即可
- 返回虚拟结点的下一个接待
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode newHead = new ListNode(-1);
ListNode tmp = newHead;
while(list1 != null && list2 != null){
if(list1.val < list2.val){
tmp.next = list1;
list1 = list1.next;
tmp = tmp.next;
}else{
tmp.next = list2;
list2 = list2.next;
tmp = tmp.next;
}
}
if(list1 == null){
tmp.next = list2;
}
else{
tmp.next = list1;
}
return newHead.next;
}
}相交链表
思路：
- 分别用两指针遍历A，B两链表，求出长度
求长度差值，因为是Y性，所有相同结点后面的长度是一样的
求出差值后，让长的走完这段差值，两个再同时走
最后判断如果两指针相等，则返回相等结点
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int szA = 0;
int szB = 0;
ListNode curA = headA;
ListNode curB = headB;
//求A链表长度
while(curA != null){
curA = curA.next;
szA++;
}
//求B链表长度
while(curB != null){
curB = curB.next;
szB++;
}
curA = headA;
curB = headB;
if(szA > szB){
//求差值，因为是Y性，所有相同结点后面的长度是一样的，所以求差值，让长的走完这段差值，两个再同时走
int diff = szA - szB;
while(diff != 0){
curA = curA.next;
diff--;
}
}
else{
int diff = szB - szA;
while(diff != 0){
curB = curB.next;
diff--;
}
}
while(curA != curB){
/* if(curA == null){
return null;
}*/ //判不判断无所谓，因为最后都会返回空
curA = curA.next;
curB = curB.next;
}
return curA;
}
}移除链表元素
思路：
- 创建两个指针
- 一个为cur用来遍历链表，找出要删除的元素
- 另一个为dp指向cur上一个结点
- dp的next指向cur的next结点，同时使cur指向下一个结点，达到删除多个结点的目的
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head == null){
return null;
}
ListNode cur = head;
ListNode dp = cur;
while(cur != null) {
if (cur.val == val) {
dp.next = cur.next;//其实这里可以不用找前一个结点，直接插入结点，交换值即可
cur = dp.next;
} else {
dp = cur;
cur = cur.next;
}
}
if(head.val == val){
head = head.next;
}
return head;
}
}反转链表
思路
- 创建一个cur指针，指向头结点的next
- 将头节点置空，作为反转后的尾结点
- 创建一个curNext指针，让他始终指向cur的next
- 让将head指针当作cur的上一个结点用，将head的结点的地址赋给cur的next，让cur指向curNext，curNext指向cur的next循环即可
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null){
return null;
}
if(head.next == null){
return head;
}
ListNode cur = head.next;
head.next = null;
while(cur != null){
ListNode curNext = cur.next;
cur.next = head;
head = cur;
cur = curNext;
}
return head;
}
}链表的中间结点
思路：
- 通过快慢指针遍历链表即可
- fast指向null或者fast.next指向null的时候停下，此时慢指针便是中间结点
class Solution {
public ListNode middleNode(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;
}
return slow;
}
}链表中倒数第K个结点
思路：
- 创建快慢指针
- 让快指针先走K-1步
- 再让快指针和慢指针同时向后一步一步挪动
- fast指向空时，slow指针指向的便是倒数第K个元素
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(k <= 0 || head == null){
return null;
}
ListNode fast = head;
ListNode slow = head;
while(k-1 != 0){
fast = fast.next;
if(fast == null){
return null;//k过大
}
k--;
}
while(fast.next != null){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
