交换链表节点
题目链接
思路
递归交换，注意递归退出条件
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode node = head.next;
head.next = swapPairs(node.next);
node.next = head;
return node;
}
虚拟节点交换
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode first,sec,cur=dummy;
while(cur.next != null && cur.next.next != null) {
first = cur.next;
sec = cur.next.next;
ListNode tmp = sec.next;
sec.next = first;
first.next = tmp;
cur.next = sec;
cur = first;
}
return dummy.next;
}
删除倒数第n个节点
题目链接
思路
快慢指针，快指针先移动n个元素
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode fast = dummy, slow = dummy;
while(n-- >= 0) {
fast = fast.next;
}
while(fast != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
链表相交
题目链接
思路
两个指针分别走A和B链表，最终一定会相交
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode A = headA, B = headB;
while(A!=B) {
if(A == null) {
A = headB;
}
else {A = A.next;}
if(B == null) {
B = headA;
}
else {
B = B.next;
}
}
return A;
}
长链表先走n步
int alen = 0, blen = 0;
ListNode A = headA, B = headB;
while(A != null) {
A = A.next;
alen++;
}
while(B != null) {
B = B.next;
blen++;
}
if (alen <blen) {
int count = blen - alen;
while (count-->0) {
headB = headB.next;
}
} else {
int count = alen - blen;
while(count-->0) {
headA = headA.next;
}
}
while( headA != null && headA != headB) {
headA=headA.next;
headB = headB.next;
}
return headA == headB ? headA : null;
环形链表
题目链接
思路
这个感觉属于数学分析题，代码实际不复杂。
快慢指针直到相遇，然后从链表头继续走直到相遇
public 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) {
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}