1、两两交换链表中的节点
题目：给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
思路：
1、考虑双指针，设置成一前一后分别指向哑节点和头节点。
2、交换时，p1.next先指向p2.next，然后p2.next再指向p2.next.next，最后将p1.next.next指向p2。借用代码随想录的图，不过我的想法将他的步骤二和步骤三互换了顺序，不需要再声明一个中间节点。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode p1 = dummy;
ListNode p2 = dummy.next;
if (p2 == null || p2.next == null) {
return dummy.next;
}
while (p2 != null && p2.next != null) {
p1.next = p2.next;
p2.next = p2.next.next;
p1.next.next = p2;
p1 = p1.next.next;
p2 = p2.next;
}
return dummy.next;
}
}
2、删除链表的倒数第N个节点
题目链接/文章讲解/视频讲解：
https://programmercarl.com/0019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9.html
题目：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
思路：
1、因为不知道链表的长度，所以一个最直接的想法就是，遍历一遍链表得到链表的长度后，再删除第size-n+1个节点。
2、还有一种更快的想法就是设置快慢指针，快指针比慢指针快n个节点，当快指针到达链表尾部时，慢指针刚好到达要删除节点的前缀节点。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy, slow = dummy;
for (int i = 0; i <= n; i++) {
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
3、链表相交
题目：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
思路：
1、如果存在一个头节点是空，则直接返回null。
2、因为是找相交的起始节点，但由于两个链表长度可能是不一致，而尾部相交部分是对齐的，则可以想方法使得两个链表对齐遍历。
3、一个想法是：分别遍历得到两个链表的长度，长链表先遍历完与短链表相差的节点数后，剩下与短链表对齐同时遍历，直到找到相交节点。
4、另一个想法是：指针A先遍历headA连接的链表，再遍历headB连接的链表，而指针B先遍历headB连接的链表，再遍历headA连接的链表，这样他们遍历的长度一致，可以同时到达相交节点。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode currA = headA;
ListNode currB = headB;
while (currA != currB) {
currA = currA == null ? headB : currA.next;
currB = currB == null ? headA : currB.next;
}
return currA;
}
}
4、环形链表II
题目链接/文章讲解/视频讲解：
https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html
题目：给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
ListNode slow = head, fast = head;
while (fast != null) {
slow = slow.next;
if (fast.next != null) {
fast = fast.next.next;
} else {
return null;
}
if (fast == slow) {
ListNode ptr = head;
while (ptr != slow) {
ptr = ptr.next;
slow = slow.next;
}
return ptr;
}
}
return null;
}
}