两两交换链表节点
/**
* 链表节点定义
*/
class LinkedListNode {
int data;
LinkedListNode next;
LinkedListNode(int value) { this.data = value; }
}
public class LinkedListUtils {
public static LinkedListNode swapPairs(LinkedListNode start) {
if (start == null || start.next == null) return start;
LinkedListNode second = start.next;
LinkedListNode newHead = swapPairs(second.next);
second.next = start;
start.next = newHead;
return second;
}
}
删除倒数第N个节点
/**
* 链表节点定义
*/
class LinkedListNode {
int data;
LinkedListNode next;
LinkedListNode(int value) { this.data = value; }
}
public class LinkedListUtils {
public static LinkedListNode removeNthFromEnd(LinkedListNode head, int n) {
LinkedListNode sentinel = new LinkedListNode(0);
sentinel.next = head;
LinkedListNode slow = sentinel;
LinkedListNode fast = sentinel;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return sentinel.next;
}
}
链表相交节点查找
/**
* 链表节点定义
*/
class LinkedListNode {
int data;
LinkedListNode next;
LinkedListNode(int value) { this.data = value; }
}
public class LinkedListUtils {
public static LinkedListNode getIntersectionNode(LinkedListNode list1, LinkedListNode list2) {
int length1 = 0, length2 = 0;
LinkedListNode cursor1 = list1, cursor2 = list2;
// 计算链表长度
while (cursor1 != null) { cursor1 = cursor1.next; length1++; }
while (cursor2 != null) { cursor2 = cursor2.next; length2++; }
// 对齐起始位置
while (length1 > length2) { list1 = list1.next; length1--; }
while (length2 > length1) { list2 = list2.next; length2--; }
// 查找相交节点
while (list1 != list2) {
list1 = list1.next;
list2 = list2.next;
}
return list1;
}
}
环形链表入口检测
/**
* 链表节点定义
*/
class LinkedListNode {
int data;
LinkedListNode next;
LinkedListNode(int value) { this.data = value; }
}
public class LinkedListUtils {
public static LinkedListNode detectCycleEntry(LinkedListNode head) {
LinkedListNode quick = head;
LinkedListNode slow = head;
// 检测是否存在环
while (quick != null && quick.next != null) {
quick = quick.next.next;
slow = slow.next;
if (quick == slow) break;
}
// 无环情况处理
if (quick == null || quick.next == null) return null;
// 寻找入口点
while (head != slow) {
head = head.next;
slow = slow.next;
}
return head;
}
}
