目录
四、链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)
六、链表分割_牛客题霸_牛客网 (nowcoder.com)
七、链表的回文结构_牛客题霸_牛客网 (nowcoder.com)
十、 142. 环形链表 II - 力扣（LeetCode）
我们遍历一次链表来解决这个问题。首先我们定义两个节点，ListNode cur = head.next;
ListNode prve = head;在while（cur != null）{ } 循环里判断是否等于要删除的元素,当等于要删除的元素时:
当不等于要删除的元素时:
最后在单独判断一下头结点:
if(head.val == key){
head = head.next;
}完整代码展示:
public ListNode removeElements(ListNode head, int key) {
if (head == null){
return null;
}
ListNode cur = head.next;
ListNode prve = head;
while (cur != null){
if(cur.val == key){
prve.next = cur.next;
cur = cur.next;
}else{
prve = cur;
cur = cur.next;
}
}
if(head.val == key){
head = head.next;
}
return head;
}二、206. 反转链表 - 力扣（LeetCode）
我们可以先定义一个head.next节点，然后再将头结点置为null：
ListNode cur = head.next;
head.next = null;然后我们在循环里面需要记住cur.next，所以定义一个curNext = cur.next：
然后我们运用头插法，将cur插入到head前面，再移动head和cur和curNext：
当然在一开始需要判断head和head.next是否为空，完整代码如下：
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;
}三、876. 链表的中间结点 - 力扣（LeetCode）
这个题在遍历一次链表的情况下，我们可以使用快慢指针：
即定义一个fast指针一次走两步，slow指针一次走一步，再遍历整个链表，当fast指针指向空时，slow指针便指向的是链表的中间位置。也会有两种情况，链表的长度为奇数和偶数时。
奇数时：
偶数时：
完整代码：
public ListNode middleNode(ListNode head) {
if (head == null){
return null;
}
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}注：fast != null && fast.next != null 这两个的顺序不能调换,否则会空指针异常(先判断fast.next 是否为空时,fast已经是空了).
四、链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)
这道题我们还是运用了快慢指针的思想：
定义fast和slow指针，先让fast指针走k-1步，再两个指针一起走，直到fast.next为空。当然首先要判断k值是否合理,可以在fast指针走k-1步时实现；
代码如下：
public ListNode FindKthToTail(ListNode head, int k){
if (head == null || k <= 0){
return null;
}
ListNode slow = head;
ListNode fast = head;
while (k-1 != 0){
fast = fast.next;
if (fast == null){ //判断k是否合理
return null;
}
k--;
}
while (fast.next != null){
fast = fast.next;
slow = slow.next;
}
return slow;
}五、21. 合并两个有序链表 - 力扣（LeetCode）
我们可以先实例化一个虚拟节点，然后在while(head1 != null && head2 != null){} 的时候,比较一下head1.val和head2.val的大小,将小的节点放到虚拟节点后面,,最后遍历完一个链表时,将剩下的链表整合到一起.
完整代码:
public ListNode mergeTwoLists(ListNode head1, ListNode head2) {
ListNode newHead = new ListNode(-1);//虚拟节点
ListNode tmp = newHead;
while (head1 != null && head2 != null) {
if (head1.val < head2.val) {
tmp.next = head1;
head1 = head1.next;
tmp = tmp.next;
} else {
tmp.next = head2;
head2 = head2.next;
tmp = tmp.next;
}
}
if (head1 != null) {
tmp.next = head1;
}
if (head2 != null) {
tmp.next = head2;
}
return newHead.next;
}六、链表分割_牛客题霸_牛客网 (nowcoder.com)
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针：
- 这道题我们可以先分割再将它们串起来，先实例化两个结点 bs 和 as（before start，after start）
- 遍历链表，将小于 x 的结点用尾插法插入到 bs 后，将大于 x 的结点用尾插法插入到 as后
- 再实例化两个结点 be 和 ae（before end ，after end）作为两个结点的终点，再把 be 和 ae 串起来，返回 bs ，就得到了分割后的链表了
下面我们来具体的实现代码：
public ListNode partition(ListNode head, int x) {
ListNode bs = null;
ListNode be = null;
ListNode as = null;
ListNode ae = null;
ListNode cur = head;
while (cur != null){
if(cur.val < x){
//插入到第一个段【尾插法】
if(bs == null){
//这是第一次插入元素
bs = cur;
be = cur;
}else{
be.next = cur;
be = be.next;
}
}else {
//插入到第二个段【尾插法】
if (as == null) {
//这是第一次插入元素
as = cur;
ae = cur;
} else {
ae.next = cur;
ae = ae.next;
}
}
cur = cur.next;
}
//当没有小于x的结点时，bs就是null
if(bs == null){
return as;
}
//将be和as串起来
be.next = as;
//ae.next不一定null，需要手动将其置空
if(as != null){
ae.next = null;
}
return bs;
}七、链表的回文结构_牛客题霸_牛客网 (nowcoder.com)
这道题的思路如下：
- 首先通过快慢指针找到链表的中间位置
- 然后从中间位置到末尾进行翻转链表（翻转单链表）
- 最后一边从头一边从末尾开始遍历链表并且比较val值是否相等，知道相遇结束
public boolean chkPalindrome(ListNode head) {
if(head == null){
return true;
}
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;
}
//两头开始遍历比较val值是否相同
while (head != slow){
if (head.val != slow.val){
return false;
}
if (head.next == slow){//两边相遇了
return true;
}
head = head.next;
slow = slow.next;
}
return true;
}八、160. 相交链表 - 力扣（LeetCode）
思路：
- 本题中两个链表相交是 Y 字形的，且相交的点的地址是相同。
- 需要先求出两个链表的差值，因为两个链表的长度不一定相同，其相交之前的部分不一定相同，但是其相交的话相交之后的部分长度一定相同：
- 让最长的链表走差值步
- 然后再让两个链表一起走，相遇点就是相交的节点
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//分别求出两个链表的长度
int lenA = 0;
int lenB = 0;
ListNode p1 = headA;//代表永远指向长的链表
ListNode p2 = headB;//代表永远指向短的链表
while(p1 != null){
lenA++;
p1 = p1.next;
}
while (p2 != null){
lenB++;
p2 = p2.next;
}
p1 = headA;
p2 = headB;
//求出差值
int len = lenA - lenB;
if(len < 0){
p1 = headB;//代表永远指向长的链表
p2 = headA;//代表永远指向短的链表
len = lenB - lenA;//len一定是一个正数
}
//让长的链表走了差值步
while (len != 0){
p1 = p1.next;
len--;
}
//找到相同的点，直到相遇
while(p1 != p2){
p1 = p1.next;
p2 = p2.next;
}
return p1;
}九、141. 环形链表 - 力扣（LeetCode）
思路：
- 还是运用了快慢指针的思想，定义一个fast结点和一个slow结点。
- slow走一步，fast走两步：因为如果链表带环，按照这样走的话，fast和slow最差的情况就是相差一圈，然后就会慢慢逼近。
- 如果是slow走一步，fast走三步四步的情况下，slow和fast就会相遇的很慢，或者就会永远的错过。
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
return true;
}
}
return false;
}十、 142. 环形链表 II - 力扣（LeetCode）
思路：
- 这道题运用到了上一题的的找环的方法，然后还要找到环的入口。
- 我们可以设起始点到入口点的距离为X，入口点到相遇点的距离为Y，环的长度为C，因为fast的速度是slow的两倍，所以距离也是两倍，fast的路程为：X + C + （C - Y），slow的路程为：X + C - Y，便可以联立等式：2（X + C - Y）= X + C + (C - Y),化简可以得到 X = Y,所以当slow和fast相遇之后，我们可以让slow = head，slow走X这段距离,fast刚好是走Y这段距离,因为距离相同,所以他们相遇的地方就是入口点:
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = 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;
}
slow = head;
while (slow != fast){
slow = slow.next;
fast = fast.next;
}
return fast;
}