文章目录
24. 两两交换链表中的节点
题目描述
思路分析
递归思路
代码
- 虚拟头节点
写法一：
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
ListNode pre = dummyNode;
while(pre.next != null && pre.next.next != null){
ListNode temp = head.next.next;
pre.next = head.next;
head.next.next = head;
head.next = temp;
pre = head;
head = head.next;
}
return dummyNode.next;
}
}
写法二：
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
ListNode pre = dummyNode;
while(pre.next != null && pre.next.next != null){
ListNode temp = pre.next;
ListNode temp1 = pre.next.next.next;
pre.next = pre.next.next;
pre.next.next = temp;
pre.next.next.next = temp1;
pre = pre.next.next;
}
return dummyNode.next;
}
}
- 递归
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode next = head.next;
head.next = swapPairs(next.next);
next.next = head;
return next;
}
}
19. 删除链表的倒数第 N 个结点
题目描述
思路分析
删除节点的关键是找到其前一个的指针
- fast首先走n 步
- fast和slow同时移动，直到fast指向末尾
- 删除slow指向的节点（如果走n+1步，正好slow指向前一个）
代码
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummyNode = new ListNode(-1);
ListNode slow = dummyNode;
ListNode fast = dummyNode;
dummyNode.next = head;
while(n-- > 0 && fast != null){
fast = fast.next;
}
ListNode pre = null;
while(fast != null){
pre = slow;//前一个指针
slow = slow.next;
fast = fast.next;
}
pre.next = slow.next;
return dummyNode.next;
}
}
面试题 02.07. 链表相交
同：160.链表相交
题目描述
思路分析
-
法1
求出两个链表的长度，并求出两个链表长度的差值，然后让两链表末尾对齐
-
法2
设「第一个公共节点」为 node ，「链表 headA」的节点数量为 a ，「链表 headB」的节点数量为 bb ，「两链表的公共尾部」的节点数量为 c ，则有：- 头节点 headA 到 node 前，共有 a - c 个节点；
- 头节点 headB 到 node 前，共有 b - c 个节点；
考虑构建两个节点指针 A? , B 分别指向两链表头节点 headA , headB ，做如下操作：
指针 A 先遍历完链表 headA ，再开始遍历链表 headB ，当走到 node 时，共走步数为：
a + (b - c)
a + (b - c)
指针 B 先遍历完链表 headB ，再开始遍历链表 headA ，当走到 node 时，共走步数为：
b + (a - c)
b + (a - c)
如下式所示，此时指针 A , B 重合，并有两种情况：
a + (b - c) = b + (a - c)
- 若两链表 有 公共尾部 (即 c > 0) ：指针 A , B 同时指向「第一个公共节点」node 。
- 若两链表 无 公共尾部 (即 c = 0c=0 ) ：指针 A , B 同时指向 null。
代码
- 法1
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA = headA;
ListNode curB = headB;
int lenA = 0;
int lenB = 0;
while(curA != null){
lenA++;
curA = curA.next;
}
while(curB != null){
lenB++;
curB = curB.next;
}
curA = headA;
curB = headB;
if(lenB > lenA){
int tempLen = 0;
tempLen = lenA;
lenA = lenB;
lenB = tempLen;
ListNode tempNode = null;
tempNode = curA;
curA = curB;
curB = tempNode;
}
int gap = lenA - lenB;
while(gap-- > 0){
curA = curA.next;
}
while(curA != null){
if(curA == curB){
return curA;
}
curA = curA.next;
curB = curB.next;
}
return null;
}
}
- 法2
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode pA = headA;
ListNode pB = headB;
while(pA != pB){
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
}
142.环形链表II
题目表述
思路分析
- 环的判断
快慢指针法：fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。 - 环的入口
相遇时候：slow走：x+y || fast走： x+y+n*(y+z)
等式 x+y = x+y+n*(y+z)
化简 x = n (y + z) - y
x = (n - 1) (y + z) + z
x = z：n为1的情况来举例，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了。
从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。
代码
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 index = fast;
ListNode index1 = head;
while(index != index1){
index1 = index1.next;
index = index.next;
}
return index;
}
}
return null;
}
}