24.两两交换链表中的节点
leetcode链接：24.两两交换链表中的节点
题目：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入： head = [1,2,3,4]
输出： [2,1,4,3]
示例 2：
输入： head = []
输出： []
第一想法：
看到这道题目的第一想法是暴力，从头开始每次循环就交换两个元素，直至最后没有元素或者剩下一个元素时结束循环；但是想想这又是重复的行为，所以应该可以使用递归，多次尝试后成功解决；也可以用虚拟头节点，其实也是使用指针的思想。
方法1 利用虚拟头节点
思路
链表和数组的不同之一就是数组可以通过索引直接找到某个元素，但是链表必须借助指针遍历，所以交换链表中的两个元素必须修改设计到此两个元素前后的元素.
我们想一下，我们怎么交换链表中的两个元素？不就是通过修改节点的指针达到交换元素的目的吗？如下，我们交换要交换链表中2和3的位置：
//交换链表中node.next和node.next.next两节点 返回交换后的第一个节点 即原来的node.next.next这个节点
public ListNode swap(ListNode node) {
ListNode temp = node.next.next;//用temp保存node.next.next
node.next.next = temp.next;
temp.next = node.next;
node.next = temp;
return node;
}
交换两个元素是这样，本题也是如此，就是节点多了而已。下面使用虚拟头节点，保证对头节点与对其他元素的操作都相同。
本题Java代码：
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummyHead = new ListNode();//虚拟头节点
dummyHead.next = head;
ListNode cur = dummyHead;
while (cur.next != null && cur.next.next != null) {
ListNode node = cur.next.next;
cur.next.next = node.next;
node.next = cur.next;
cur.next = node;
cur = cur.next.next;
}
return dummyHead.next;//返回交换后链表的头节点
}
}
方法2 递归
Java代码：
class Solution {
public ListNode swapPairs(ListNode head) {
//当递归完所有元素（head==null）或者剩下一个元素（head.next==null）时
//直接返回head
if(head == null || head.next == null) {
return head;
}
//保存下一个节点
ListNode next = head.next;
//递归 对下一个节点之后的元素进行两两交换，保存交换后返回的第一个元素
ListNode newNode = swapPairs(next.next);
//交换
next.next = head;
head.next = newNode;
return next;
}
}
19.删除链表的倒数第N个节点
题目：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
leetcode链接: 19.删除链表的倒数第N个节点
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
方法：快慢指针
思路:
设置快慢指针，起初快慢指针fast和slow都指向头节点，然后快指针先走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 dummyHead = new ListNode();
dummyHead.next = head;
ListNode fast = dummyHead;
ListNode slow = dummyHead;
for(int i = 0; i < n; i++) {
fast = fast.next;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
//此时slow已经指向待删除元素的前一个元素
ListNode delNode = slow.next;
slow.next = slow.next.next;
delNode.next = null;
return dummyHead.next;
}
}
面试题 02.07. 链表相交
leetcode链接：面试题 02.07. 链表相交
题目：
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例1
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at ‘8’
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例2
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at ‘2’
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例3
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
思路：
其实题目说的让人迷迷糊糊的，其实要注意所求交点不是数值相等，而是指针相等。
（1）让carA和curB指向对应链表的头节点
（2）让较长链表的指针往后移动，至与curB末尾对齐的位置（要先得到两条链表的长度差）
（3）此时比较curA与curB所指节点数值是否相等，若不相等则让两个指针同时向后移动，若相等则为所求交点，返回该焦点即可。
Java代码：
/**
* 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) {
//（1）
ListNode curA = headA;
ListNode curB = headB;
//（2）
int lengthA = 0;//用来记录A链表的长度
int lengthB = 0;//用来记录B链表的长度
while(curA != null) {
lengthA++;
curA = curA.next;
}
while(curB != null) {
lengthB++;
curB = curB.next;
}
curA = headA;//让 curA 重新指向 headA
curB = headB;//让 curB 重新指向 headB
if(lengthA < lengthB) {
//如果A链表长度小于B链表长度 就交换lendthA和lengthB的值 以保证后面长度差 lengthA - lengthB 是正值；
int temp = lengthA;
lengthA = lengthB;
lengthB = temp;
//如果A链表长度小于B链表长度 就交换 curA 和 curB 指针，让curA指向B链表的头节点，curB指向A链表的头节点
ListNode tNode = curA;
curA = curB;
curB = tNode;
}
int dlength = lengthA - lengthB;
while(dlength != 0) {
curA = curA.next;
dlength--;
}
//(3)
while(curA != null) {
if(curA == curB) {
return curA;
}
curA = curA.next;
curB = curB.next;
}
return null;
}
}
142.环形链表2
leetcode链接：142.环形链表2
题目：
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。
注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
参考文章：142.环形链表II
Java代码：
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
ListNode index1 = fast;
ListNode index2 = head;
while (index1 != index2) {
index1 = index1.next;
index2 = index2.next;
}
return index2;
}
}
return null;
}
}
链表总结
链表理论基础：
链表理论基础
很多链表题目都可以用虚拟头节点、指针、递归这些方法来解决，因此熟练使用这些方法，明确各种方法的注意事项非常重要！
虚拟头节点
因为对链表当前节点的操作必须要找到其前一个节点才行，而头节点没有头一个节点，所以可以设置一个虚拟头节点指向头节点，以保证对头节点的操作与对其他节点的操作都一致！这就是虚拟头节点的好处！
指针
无论是单指针还是双指针，关键还是关键是如何定义和移动指针，指针从哪里开始，移动的条件是什么，啥时候移动，移动的目的是什么，移动后要继续判断什么，啥时候结束，都一定要清晰明确！
递归
重复性操作就可以使用递归，但要注意递归的终止条件是什么！