LinkedList
反转链表
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode last = reverseList(head.next);
// 此时head的next是逆链表的尾 (2)，但尾(2)的next是null，所以把head.next.next(tail) = head, 再把head.next换成null，反转就完成了
head.next.next = head;
head.next = null;
return last;
}
反转前N节点
ListNode postHead = null;
public ListNode reverseN(ListNode head, int count) {
if(count = 1){
postHead = head.next;
return head;
}
ListNode last = reverseList(head.next, count - 1);
// 此时head的next是逆链表的尾，但尾的next是null，所以把head.next.next(tail) = head, 再把head.next换成null，反转就完成了
head.next.next = head;
// postHead是需反转之后的正序链表的头
head.next = postHead;
return last;
}
k个一组反转
力扣
public ListNode reverseKGroup(ListNode head, int k) {
// 先分割出需要反转的一组
ListNode start = head, tail = head;
for(int i = 0; i < k; i++){
if(tail == null){
return head;
}
tail = tail.next;
}
start.next = reverse(start, tail);
ListNode newHead = reverseKGroup(tail, k);
return newHead;
}
ListNode reverse(ListNode a, ListNode b) {
ListNode pre, cur, nxt;
// pre是反转好的头, cur起指针作用, nxt就是下一个节点
pre = null; cur = a; nxt = a;
while(cur != b){ // 到b就结束
nxt = cur.next; // 跟cur = nxt一起，交换当前节点和下一个节点的位置
cur.next = pre; //头尾互换，（三个为一组）
pre = cur; // 让中间的值变为头
cur = nxt; // 前进
}
// 返回反转后的头结点
return pre;
}
merge-two-sorted-lists
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 虚拟头结点
ListNode dummy = new ListNode(-1), p = dummy;
ListNode p1 = list1, p2 = list2;
while (p1 != null && p2 != null) {
// 比较 p1 和 p2 两个指针
// 将值较小的的节点接到 p 指针
if (p1.val > p2.val) {
p.next = p2;
p2 = p2.next;
} else {
p.next = p1;
p1 = p1.next;
}
// p 指针不断前进
p = p.next;
}
if (p1 != null) {
p.next = p1;
}
if (p2 != null) {
p.next = p2;
}
return dummy.next;
}
基于一个节点按大小分割
一个链表中储存的元素大小都小于 x，另一个链表中的元素都大于等于 x，最后再把这两条链表接到一起
public ListNode partition(ListNode head, int x) {
ListNode smallerHead = new ListNode(-1);
ListNode largerHead = new ListNode(-1);
ListNode smaller = smallerHead, larger = largerHead;
ListNode dummyHead = head;
while (dummyHead != null) {
if (dummyHead.val >= x) {
larger.next = dummyHead;
larger = larger.next;
} else {
smaller.next = dummyHead;
smaller = smaller.next;
}
// 断开原链表中的每个节点的 next 指针, 预防cycle
ListNode temp = dummyHead.next;
dummyHead.next = null;
dummyHead = temp;
}
smaller.next = largerHead.next;
return smallerHead.next;
}
merge n个 sorted-lists
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) return null;
ListNode dummyHead = new ListNode(-1);
ListNode p = dummyHead;
// 优先级队列，根据head排序
PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length, (a, b)->(a.val - b.val));
for (ListNode head : lists) {// 将链表的头加入最小堆
if (head != null)
pq.add(head);
}
while (!pq.isEmpty()) {
ListNode node = pq.poll(); // 获取最小节点，poll is get and remove
p.next = node;
if (node.next != null) {
pq.add(node.next);
}
// p 指针不断前进
p = p.next;
}
return dummyHead.next;
}
返回链表的倒数第 k 个节点
ListNode findFromEnd(ListNode head, int k) {
ListNode p1 = head;
// p1 先走 k 步
for (int i = 0; i < k; i++) {
p1 = p1.next;
}
ListNode p2 = head;
// p1 和 p2 同时走 n - k 步
while (p1 != null) {
p2 = p2.next;
p1 = p1.next;
}
// p2 现在指向第 n - k + 1 个节点，即倒数第 k 个节点
return p2;
}
remove-nth-node-from-end
用到了前面的返回倒数第n节点的逻辑
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummyHead = new ListNode(-1, head);
ListNode k1 = dummyHead;
ListNode k2 = dummyHead;
for(int i = 0; i < n + 1; i++){
k1 = k1.next;
}
while(k1!=null){
k2 = k2.next;
k1 = k1.next;
}
k2.next = k2.next.next;//跳过一个节点以达成删除的效果
return dummyHead.next;
}
链表的中间点
快慢指针，快指针一次跳两个，这样就变相进行了len/2的操作
public ListNode middleNode(ListNode head) {
ListNode fast = head, slow = head;
while(fast != null && fast.next != null){ // 两种情况以防止单数和双数个节点的链表出现null pointer
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
两个链表是否相交
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// 计算两条链表的长度
int lenA = 0, lenB = 0;
for (ListNode p1 = headA; p1 != null; p1 = p1.next) { lenA++; }
for (ListNode p2 = headB; p2 != null; p2 = p2.next) { lenB++; }
// 让 p1 和 p2 到达尾部的距离相同, (比如p1长就先在p1走n步)
ListNode p1 = headA, p2 = headB;
if (lenA > lenB) {
for (int i = 0; i < lenA - lenB; i++) {
p1 = p1.next;
}
} else {
for (int i = 0; i < lenB - lenA; i++) {
p2 = p2.next;
}
}
// 1、不相交，他俩同时走到尾部空指针
// 2、相交，他俩走到两条链表的相交点，那么while结束，返回p1或者p2其实都一样
while (p1 != p2) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
第二解法
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// p1 指向 A 链表头结点，p2 指向 B 链表头结点
ListNode p1 = headA, p2 = headB;
while (p1 != p2) {
// p1 走一步，如果走到 A 链表末尾，转到 B 链表
if (p1 == null) p1 = headB;
else p1 = p1.next;
// p2 走一步，如果走到 B 链表末尾，转到 A 链表
if (p2 == null) p2 = headA;
else p2 = p2.next;
}
return p1;
}
链表是否包含环
boolean hasCycle(ListNode head) {
// 也是用快慢指针，如果慢指针被快指针追上了，说明有个环，快指针绕了一圈
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) { // 快慢指针碰面，说明含有环
return true;
}
}
return false;
}
找到环的起点
ListNode detectCycle(ListNode head) {
ListNode fast = head, slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break; // 如果相遇，break
}
// 这里跟检测有没有环一样
if (fast == null || fast.next == null) {
return null; // fast 遇到空指针说明没有环
}
slow = head; // 慢节点重新指向头结点
// 快慢指针同步前进，相交点就是环起点
while (slow != fast) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
回文
还有一种方法是用快慢指针找到中点，然后反转左边的链表，再同步.next比较是否一致
ListNode left;
public boolean isPalindrome(ListNode head) {
left = head;
return traverse(head);
}
boolean traverse(ListNode right){
if(right == null){
return true;
}
boolean result = traverse(right.next); //递归
result = result && (right.val == left.val); //目前最右跟最左是不是一样，
left = left.next; // 比较完成，左边进一，比较倒数第二个以此类推
return result;
}