两两交换链表中的节点(力扣24.)
- dummyhead .next = head;
- cur = dummyhead;
- while(cur.next!=null&&cur.next.next!=null)
- temp = cur.next;
- temp1=cur.next.next.next;
- cur.next= cur.next.next;
- cur.next.next=temp;
- temp.next=temp1;
- cur = cur.next.next;
- return dummyhead.next;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
//只是用一个temp指针
ListNode dummyHead = new ListNode();
dummyHead.next = head;
ListNode cur = dummyHead;
while(cur.next != null && cur.next.next != null){
//临时指针存储cur的next，因为在操作后会变成孤立节点
ListNode temp = cur.next;
//操作进行
cur.next = cur.next.next;
temp.next = cur.next.next;
cur.next.next = temp;
//下一循环
cur = cur.next.next;
}
return dummyHead.next;
}
}
删除链表的倒数第N个结点
- 双指针
- 等距离双指针删除链表倒数第N个元素，注意指针应该停留在删除目标的前一个元素
- 为实现上述目标可以令快指针先走n+1步且终止条件为fast==null
- 或者快指针先走n步且终止条件为fast.next==null，以下方法使用第二种
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//双指针
ListNode dummyHead = new ListNode();
dummyHead.next = head;
ListNode cur = dummyHead;
ListNode post = dummyHead;
while(n > 0){
post = post.next;
if(post == null){
return null;
}
n--;
}
while(post.next != null){
post = post.next;
cur = cur.next;
}
if(cur.next != null){
cur.next = cur.next.next;
}else{
cur.next = null;
}
return dummyHead.next;
}
}
面试题：链表相交（力扣面试题02.07）
- 简单来说，就是求两个链表交点节点的指针。 交点不是数值相等，而是指针相等。
- 我们求出两个链表的长度，并求出两个链表长度的差值，并令curA为长度更大的一方。然后让curA移动到，和curB 末尾对齐的位置，然后以此求两指针是否相同
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA = headA;
ListNode curB = headB;
int lenA = 0;
int lenB = 0;
while(headA != null){
headA = headA.next;
lenA++;
}
while(headB != null){
headB = headB.next;
lenB++;
}
headA = curA;
headB = curB;
if(lenA < lenB){
ListNode temp = headB;
headB = headA;
headA = temp;
int tempInt = 0;
tempInt = lenB;
lenB = lenA;
lenA = tempInt;
}
int gap = lenA - lenB;
while(gap != 0){
headA = headA.next;
gap--;
}
while(headA != null){
if(headA == headB){
return headA;
}
headA = headA.next;
headB = headB.next;
}
return null;
}
}
环形链表（力扣142.）
- 判断链表是否有环
- 返回环的入口（如果存在）
- 快慢双指针判断是否有环：
- 快指针每次走两个结点，慢指针每次走一个结点
- 快指针对于慢指针的相对速度是每次一个结点
- 因此快指针和慢指针一定会在环里相遇
- y + z = 一圈；且y为慢指针在圈内走过的距离
- slow = x + y
- fast = x + y + n(y + z)//n为fast多余圈数
- 又因为fast = 2 * slow
- x + y + n(y+z) = 2(x + y)
- x = n(y + z) - y;
- 其中n应该大于等于1
- x = (n - 1)(y + z) + z;
- n=1时，x=z;两指针会在环入口相遇
- n!= 1 时，同理
- 即从相遇的地方开始，与起点开始的指针以相同速度移动，最后相遇的点就是入口
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
//快慢指针，从快慢指针交界点开始与另一指针从头节点开始以相同速度进行，交点即为环入口
ListNode fast = head;
ListNode slow = head;
ListNode target = head;
if(fast == null){
return null;
}
while(fast.next!= null &&fast.next.next !=null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
break;
}
}
if(fast.next == null||fast.next.next==null){
return null;
}
while(target != slow){
slow = slow.next;
target = target.next;
}
return target;
}
}