题目一：
public ListNode removeElements(ListNode head, int val) {
//1. 如果链表为null，直接返回head
if (head == null) {
return head;
}
//2. 定义快慢指针
ListNode pre = head;
ListNode del = pre.next;
while (pre.next != null) {
if (del.val == val) {
pre.next = del.next;
//del = del.next;
} else {
pre = pre.next;
//del = del.next;
}
del = del.next;
}
//3. 排查头节点
if (head.val == val) {
head = head.next;
}
//4. 返回
return head;
}题目二：
public ListNode reverseList(ListNode head) {
//1. 如果链表为null，直接返回head
if (head == null) {
return head;
}
//2. 正常
ListNode cur = head.next;//待交换节点
//3. 将头节点的next置为null
head.next = null;
//4. 进行交换
while (cur != null) {
//5. 记录待交换节点的下一个节点
ListNode curN = cur.next;
cur.next = head;
head = cur;
cur = curN;
}
//5. 返回
return head;
}题目三：
public ListNode middleNode(ListNode head) {
//1. 题目提示：链表一定不为null
//2. 定义快慢指针
ListNode fast = head;//每次走两步
ListNode slow = head;//每次走一步
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//3. 返回
return slow;
}题目四：正
面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）
public int kthToLast(ListNode head, int k) {
//新增条件：k不一定合法
//1. 如果链表为null，k<=0
if (head == null || k <= 0) {
return -1;
}
//2. 定义快慢指针
ListNode fast = head;
ListNode slow = head;
//3. 快指针先走k-1步,同时判断k的合法性
for (int i = 0; i < k - 1; i++) {
//【解析】：当fast.next == null时，fast不能再继续走了
//if语句写在前面的原因，如果fast.next == null，往后走了之后
//fast == null，再进入if语句会造成空指针异常
if (fast.next == null) {
return -1;
}
fast = fast.next;
}
//4. 快慢指针同时走
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
//5. 返回
return slow.val;
}题目五：正
public ListNode mergeTwoLists(ListNode head1, ListNode head2) {
//1. 定义傀儡节点
ListNode head = new ListNode(-1);
ListNode cur = head;
//2. 开始拼接
while (head1 != null && head2 != null) {
if (head1.val < head2.val) {
cur.next = head1;
head1 = head1.next;
} else {
cur.next = head2;
head2 = head2.next;
}
cur = cur.next;
}
//3. 根据出循环的原因分别作出反应（即使两个链表都为空也没关系）
if (head1 == null) {
cur.next = head2;
}
if (head2 == null) {
cur.next = head1;
}
//3. 返回
return head.next;
}题目六：
public ListNode partition(ListNode pHead, int x) {
// write code here
//1. 如果链表为null
if (pHead == null) {
return pHead;
}
//2. 定义两组傀儡节点
ListNode head1 = new ListNode(-1);
ListNode cur1 = head1;
ListNode head2 = new ListNode(-1);
ListNode cur2 = head2;
//3. 遍历所给链表
while (pHead != null) {
if (pHead.val < x) {
cur1.next = pHead;
cur1 = cur1.next;
} else {
cur2.next = pHead;
cur2 = cur2.next;
}
pHead = pHead.next;
}
//4. 合并两个傀儡链表
//① 如果前一个链表为null
if (head1.next == null) {
return head2.next;
}
//② 如果前一个链表不为null（包含后一个链表为null和不为null的情况）
cur1.next = head2.next;
cur2.next = null;//最后一个节点的值给了前一个链表，则此时后一个链表的最后一个节点的next一定不是null
return head1.next;
}题目七：正
链表的回文结构_牛客题霸_牛客网 (nowcoder.com)
public boolean chkPalindrome(ListNode A) {
// write code here
//1. 如果链表为null
if (A == null) {
return true;
}
//2. 找到中间节点
ListNode fast = A;//每次走两步
ListNode slow = A;//每次走一步
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//3. 翻转中间节点之后的所有节点
ListNode cur = slow.next;//待翻转节点
while (cur != null) {
ListNode curN = cur.next;
cur.next = slow;
slow = cur;
cur = curN;
}
//4. 判断是否为回文
fast = A;
while (fast != slow) {//链表节点个数为奇数，fast==slow为结束标志
if (fast.val != slow.val) {//不对称
return false;
} else {//对称
if (fast.next == slow) {//链表节点个数为偶数，fast.next==slow为结束标志
return true;//如果是对称的条件，并且满足了偶数节点个数的结束条件，则可直接返回
}
fast = fast.next;
slow = slow.next;
}
}
//5. 返回
return true;
}题目八：正
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//题目已经提示两个链表的节点个数一定不为0
//1. 计算两个链表的长度,并假设链表A更长
int countA = 0;
int countB = 0;
ListNode curA = headA;
ListNode curB = headB;
while (curA != null) {
countA++;
curA = curA.next;
}
while (curB != null) {
countB++;
curB = curB.next;
}
//2. 判断究竟哪个链表更长
int sub = countA - countB;
curA = headA;
curB = headB;
if (sub < 0) {//此时B链表更长
curA = headB;
curB = headA;
sub = countB - countA;
}
//3. 让更长的链表先走sub步
for (int i = 0; i < sub; i++) {
curA = curA.next;
}
//4. 找相遇节点
while (curA != null) {//只用判断curA和curB中是否有一个为null即可
if (curA == curB) {
return curA;
}
curA = curA.next;
curB = curB.next;
}
//5. 代码走到这里一定是因为两个链表不相交
return null;
}题目九：正
public boolean hasCycle(ListNode head) {
//定义快慢指针（下列代码链表为null也能正确处理）
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;
}题目十：正
public ListNode detectCycle(ListNode head) {
//1. 找到快慢指针相遇的节点
//定义快慢指针（下列代码链表为null也能正确处理）
ListNode fast = head;//一次走两步
ListNode slow = head;//一次走一步
while (fast != null && fast.next != null) {//有顺序要求的原因，如果链表为空，后面的会空指针异常
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
break;
}
}
//2. 判断是如何出while循环的
//关于不能以fast != slow作为循环条件的原因
//答：当链表为null,或链表只有一个节点时，也满足该条件，
//此时则不能判定是fast==slow的情况
if (fast == null || fast.next == null) {
return null;
}
//3. 寻找入环点
fast = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
//4. 返回
return fast;
}