链表（Linked List）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针（Pointer）。
由于不必须按顺序存储，链表在插入的时候可以达到 O(1)的复杂度，比另一种线性表 —— 顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要 O(n)的时间，而顺序表相应的时间复杂度分别是 O(log\ n)和O(1)。
链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。
各题题解：
public static class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
// ###### [反转链表](https://leetcode-cn.com/problems/reverse-linked-list/) ★
/**
* 思路： 双指针迭代
* 我们可以申请两个指针，第一个指针叫 pre，最初是指向 null 的。
* 第二个指针 cur 指向 head，然后不断遍历 cur。
* 每次迭代到 cur，都将 cur 的 next 指向 pre，然后 pre 和 cur 前进一位。
* 都迭代完了(cur最后一次会被置为null)，pre 就是最后一个节点了。
* @param head
* @return
*/
public ListNode reverseList(ListNode head) {
ListNode preNode = null;
ListNode curNode = head;
while (curNode != null) {
//核心就是4步
//1.next往后移，2.cur.next指向pre
//3.pre往后移，4.cur往后移
//pre保持指向前一个节点，cur、next指向当前同一个节点
ListNode temp = curNode.next;
curNode.next = preNode;
//preNode/curNode节点往后移动
preNode = curNode;
curNode = temp;
}
return preNode;
}
// ###### [反转链表 II](https://leetcode.cn/problems/reverse-linked-list-ii/) ★
/**
* 根据上图思路：
* 1.需要快进到反转区间左位置
* 2.使用变量记住区间前一个位置和第一个位置节点
* 3.使用经典四步反转left到right区间的节点
* 4.将反转后的链表与原链表进行拼接
*/
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode pre = null, cur = head;
//cur在pre的前一个位置
for (int i=0;i<left-1;i++) {
pre = cur;
cur = cur.next;
}
//使用变量记住区间前一个位置和第一个位置节点
ListNode pre2 = pre;
ListNode cur2 = cur;
for (int i=left;i<=right;i++) {
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
//将反转后的链表与原链表进行拼接
//有一种情况，从第一个位置就开始反转，那么pre开始为null,pre2也是为null的，需要判空一下，头就指向pre，即反转区间的头节点
if (pre2 != null) {
pre2.next = pre;
} else {
head = pre;
}
cur2.next = cur;
return head;
}
// ###### [环形链表](https://leetcode-cn.com/problems/linked-list-cycle/) ★
//快慢指针：快指针单位时间移动2步，慢指针单位时间移动1步
//如果某个时候，快指针的next为null了，那么表示链表有尾节点
//否则，去判断，一定在某一时刻，快指针会超过慢指针N圈，站在同一个位置
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null) {
//要么有环，要么没有环，没有环，则最终快速指针会走完，如果没有环，
//则快速指针一定会在某个时刻追上慢速指针，即指向同一个节点
//这里要找到一个循环结束点，并返回true，否则会死循环
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
return true;
}
}
return false;
}
// ###### [环形链表 II](https://leetcode.cn/problems/linked-list-cycle-ii/)
public ListNode detectCycle(ListNode head) {
//题解：这个题的目标，是找到环的入环点，
// 根据上图，首先根据公式推导出 a = (n-1)(b+c) + c，通过这个公式，
// 再用两个指针相同速度走，相遇点就是要返回的入环节点
//那么第一步：定义一个快指针和慢指针，快指针每步走2个，慢指针每步走一个，在有环的情况下快指针一定会追上慢指针相遇
//得到相交点，构成这幅图的形式
ListNode slow = head, fast = head;
while(fast != null) {
//让慢指针每次走1步，快指针每次走2步
slow = slow.next;
if (fast.next != null) {
fast = fast.next.next;
} else {
return null;
}
if (slow == fast) {
//再构造两个慢指针走到入环节点
ListNode cur = head;
while(cur != slow) {
cur = cur.next;
slow = slow.next;
}
return cur;
}
}
return null;
}
// ###### [回文链表](https://leetcode-cn.com/problems/palindrome-linked-list/) ★
public boolean isPalindrome(ListNode head) {
ArrayList<Integer> arrayList = new ArrayList<>();
ListNode cur = head;
while(cur != null) {
arrayList.add(cur.val);
cur = cur.next;
}
int start = 0, end = arrayList.size()-1;
while(start < end) {
//将对应位置的数进行对比，只要不相等，就不是回文链表，直到start==end
if (arrayList.get(start) != arrayList.get(end)) {
return false;
}
start++;
end--;
}
return true;
}
// ###### [合并两个有序链表](https://leetcode-cn.com/problems/merge-two-sorted-lists/) ★
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode curNode = new ListNode(-1);
ListNode head = curNode;
while(l1!=null && l2!=null) {
if(l1.val <= l2.val) {
curNode.next = l1;
l1 = l1.next;
} else {
curNode.next = l2;
l2 = l2.next;
}
curNode = curNode.next;
}
curNode.next = l1==null?l2:l1;
return head.next;
}
// ######[删除链表的倒数第 N 个结点](https://leetcode.cn/problems/remove-nth-node-from-end-of-list/)
/**
* 思路：双指针法
* 1.创建虚拟节点dummy，指向head;left节点指向dummy，用来占删除位置的前一个位置
* 2.right节点指向head，将right节点移动n个位置，然后left和right继续同时往后移，直到right到达链表末尾
* 3.将left的next指向next.next
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode left = dummy; //left需要占删除位置的前一个位置
ListNode right = head;
for (int i=0;i<n;i++) { //拉开lfet 和 right节点 n个位置 ,参考链表的倒数第k个节点题
right = right.next;
}
while(right != null) { //让right节点走到链表末尾，left到达倒数第N个节点前一个节点
right = right.next;
left = left.next;
}
left.next = left.next.next;
return dummy.next;
}
// ###### [相交链表](https://leetcode-cn.com/problems/intersection-of-two-linked-lists/)
//创建两个指针 pApA 和 pBpB，分别初始化为链表 A 和 B 的头结点。然后让它们向后逐结点遍历。
//当 pApA 到达链表的尾部时，将它重定位到链表 B 的头结点 (你没看错，就是链表 B); 类似的，当 pBpB 到达链表的尾部时，将它重定位到链表 A 的头结点。
//若在某一时刻 pApA 和 pBpB 相遇，则 pApA/pBpB 为相交结点。
//为什么这种方法是可行的，因为当A、B都走到公共节点的时候，正好走了自己的路，又走了对方的路，两个指针走的距离相等
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode n1 = headA;
ListNode n2 = headB;
while(n1 != n2) {
if(n1 != null) {
//有后面节点，继续往后移动
n1 = n1.next;
} else {
n1 = headB;
}
if(n2 != null) {
n2 = n2.next;
} else {
n2 = headA;
}
}
//当n1==n2了，即各自走了一圈半到了第一个相交节点，返回n1或n2都可以
return n1;
}
// ######[两数相加](https://leetcode.cn/problems/add-two-numbers/)
/**
* 思路：模拟两个数字进行相加
* 我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。
* 具体而言，如果当前两个链表处相应位置的数字为 n1,n2，进位值为 carry，则它们的和为 n1+n2+carry；
* 其中，,答案链表处相应位置的数字为 (n1+n2+carry) % 10，而新的进位值为 (n1+n2+carry)/10
* 如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个0 。
* 此外，如果链表遍历结束后，有 carry>0，还需要在答案链表的后面附加一个节点，节点的值为 carry。
*/
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = null, tail = null; //新链表的头、尾声明
int carry = 0; //进位的值
while(l1 != null || l2 != null) {
//当两个链表不是都完了，程序就需继续按位相加
int n1 = l1!=null ? l1.val : 0;
int n2 = l2!=null ? l2.val : 0;
int cur = n1+n2+carry; //当前位置相加
if (head == null) {
//第一个节点，创建头尾节点指向新节点
tail = head = new ListNode(cur % 10);
} else {
//非第一个节点，让尾结点指向新的节点
tail.next = new ListNode(cur % 10);
tail = tail.next;
}
carry = cur / 10; //下一个的进位
//l1 l2都往后移
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
if (carry > 0) {
tail.next = new ListNode(carry);
}
}
return head;
}
// ######[两两交换链表中的节点](https://leetcode.cn/problems/swap-nodes-in-pairs/)
/**
* 操作示例： 1->2->3->4->5
* 思路：创建一个虚拟节点指向head，cur指向虚拟节点。用temp保存1和3的位置供后面连接。让cur->2, 2->1, 1->3
* 然后cur往后移动两位，即cur需要在反转的两个节点的前一个节点位置
*/
public ListNode swapPairs(ListNode head) {
ListNode dummyHead = new ListNode(0); //虚拟节点
dummyHead.next = head; //虚拟节点指向head
ListNode cur = dummyHead;
ListNode temp1, temp2;
while (cur.next != null && cur.next.next != null) {
//循环结束条件：偶数个，cur.next为null结束;奇数个，cur.next.next为null结束
temp1 = cur.next; //temp1占 1的位置
temp2 = cur.next.next.next; //temp2占 3的位置
cur.next = cur.next.next; //cur指向 2的位置
cur.next.next = temp1; //2指向1的位置
temp1.next = temp2; //1指向 3的位置
cur = cur.next.next; //cur往后移动两位
}
return dummyHead.next;
}
// ######[旋转链表](https://leetcode.cn/problems/rotate-list/)
/**
* 思路：记给定链表的长度为 n，注意到当向右移动的次数 k≥n 时，我们仅需要向右移动 k mod n 次即可。因为每 n 次移动都会让链表变为原状。
* 这样我们可以知道，新链表的最后一个节点为原链表的第 (n−1) - (k mod n) 个节点（从 0 开始计数）。
* @param head
*/
public ListNode rotateRight(ListNode head, int k) {
if (k == 0 || head == null || head.next == null) {
return head;
}
int n = 1;
ListNode iter = head;
while (iter.next != null) {
iter = iter.next;
n++;
}
int add = n - k % n;
if (add == n) {
return head;
}
iter.next = head;
while (add-- > 0) {
iter = iter.next;
}
ListNode ret = iter.next;
iter.next = null;
return ret;
}
