题目一：
删除链表中等于给定值 val 的所有节点。
【思路】：可以先想想只删除一个val怎么删的。
public ListNode removeElements(ListNode head, int val) {
//链表为空
if (head == null) {
return head;
}
//1.删除第一个节点之后所有的val
ListNode pre = head;
ListNode find = null;
while (pre.next != null) {
find = pre.next;
if (find.val == val) {
//pre本身不变，pre的next更改指向
pre.next = find.next;
} else {
//pre本省更改指向
pre = find;
}
}
//2.删除第一个节点中的val
if (head.val == val) {
head = head.next;
}
return head;
}题目二：
反转一个单链表。
public ListNode reverseList(ListNode head) {
//判断链表是否为空
if (head == null) {
return head;
}
ListNode cur = head.next;//待前移元素
//1. 将头节点的next置为null
head.next = null;
//2.开始翻转
while (cur != null) {
ListNode curN = cur.next;//写在循环里面的原因是，如果cur == null，则curN会出现空指针异常
cur.next = head;
head = cur;
cur = curN;
}
return head;
}题目三：
给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
【思路】：相同时间下，路程与速度成正比。
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个结点。
面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）
【添加条件】：判断k是否越界，且整道题只能一次遍历链表。
public int kthToLast(ListNode head, int k) {
//判断链表是否为空, 判断k是否合法
if (head == null || k <= 0) {
return -1;
}
//开始遍历
ListNode fast = head;
ListNode slow = head;
//让fast先走k-1步
for (int i = 0; i < k - 1; i++) {
fast = fast.next;
//判断k是否合法
if (fast == null) {
return -1;
}
}
//让fast和slow一起走
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
return slow.val;
}题目五：
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
【提示】：new一个新的傀儡节点
public ListNode mergeTwoLists(ListNode headA, ListNode headB) {
//定义傀儡节点(有new)
//如果不new,则要在while循环中额外判断newHead是否为nll
ListNode newHead = new ListNode();
ListNode cur = newHead;
//正常（已考虑到了haedA、headB为空的情况)
while (headA != null && headB != null) {
if (headA.val < headB.val) {
cur.next = headA;
headA = headA.next;
} else {
cur.next = headB;
headB = headB.next;
}
cur = cur.next;
}
if (headA == null) {
cur.next = headB;
}
if (headB == null) {
cur.next = headA;
}
return newHead.next;
}题目六：
以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。
public ListNode partition(ListNode head, int x) {
// write code here
ListNode curA = new ListNode(-1);
ListNode curAN = curA;
ListNode curB = new ListNode(-1);
ListNode curBN = curB;
while (head != null) {
if (head.val < x) {
curAN.next = head;
curAN = curAN.next;
} else {
curBN.next = head;
curBN = curBN.next;
}
head = head.next;
}
if (curA.next == null) {
return curB.next;
}
curAN.next = curB.next;
if (curB.next == null) {
return curA.next;
}
curBN.next = null;
return curA.next;
}题目七：
链表的回文结构。
链表的回文结构_牛客题霸_牛客网 (nowcoder.com)
public boolean chkPalindrome(ListNode head) {
// write code here
//如果不额外判断后面的代码会报空指针异常
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;
}
//while循环走完之后slow所指向的节点就是右边最后一个节点
//3.比较对应位置的前后节点
while (head != slow) {//如果节点是偶数，这两个节点永远不会相遇
if (head.val != slow.val) {
return false;
} else {
if (head.next == slow) {
return true;
}
head = head.next;
slow = slow.next;
}
}
return true;
}题目八：
输入两个链表，找出它们的第一个公共结点。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//假设链表A长于链表B
//1. 计算链表A、B的长度
ListNode curA = headA;
ListNode curB = headB;
int countA = 0;
int countB = 0;
while (curA != null) {
countA++;
curA = curA.next;
}
while (curB != null) {
countB++;
curB = curB.next;
}
//2. 判断到底哪一个链表长
int len = countA - countB;
if (len < 0) {//如果是则，链表B长
curA = headB;
curB = headA;
len = countB - countA;
} else {
//3. 让curA、B的值回归
curA = headA;
curB = headB;
}
//4. 让长链表先走len步
for (int i = 0; i < len; i++) {
curA = curA.next;
}
//5. 找节点
while (curA != curB) {//此时如果到了最后（null）也会跳出
curA = curA .next;
curB = curB.next;
}
//6. 判断是否由于为null而跳出的
if (curA == null) {
return null;
}
return curA;
}题目九：
给定一个链表，判断链表中是否有环。
【提示】：如果有环则fast和slow一定会相遇，但相遇的点不知道是环里的那点。
public boolean hasCycle(ListNode head) {
//1. 定义快慢指针
ListNode fast = head;//每次走两步
ListNode slow = head;//每次走一步
//2. 判断fast是否能==slow，head==null的情况已包含其中
//这个条件要自己举例试出来
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
return true;
}
}
return false;
}题目十：
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL。
public ListNode detectCycle(ListNode head) {
//1. 定义快慢指针
ListNode fast = head;//每次走两步
ListNode slow = head;//每次走一步
//2. 判断fast是否能==slow，head==null的情况已包含其中
//这个条件要自己举例试出来
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
break;
}
}
//如果发现没有环则这届返回null
if (fast == null || fast.next == null) {
return null;
}
//如果在环中相遇，则fast、slow此时就是相遇节点
fast = head;
//3. 找入口节点
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
}