19.删除链表的倒数第N个节点https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
思路：使用前后指针，当删除倒数第N个节点时，快慢指针之间应该间隔N个元素，当快指针到达链尾时，慢指针next指向所要删除节点。
时间复杂度：O(N)
/**
* 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) {
int i =0;
ListNode fakeHead = new ListNode();
fakeHead.next = head;
ListNode p = fakeHead;
ListNode q = fakeHead;
if(head.next==null){
return null;
}
while(p!=null){
i++;
p=p.next;
if(i>n+1){
q=q.next;
}
}
q.next=q.next.next;
return fakeHead.next;
}
}
------------------------分割线-------------------------
24. 两两交换链表中的节点https://leetcode.cn/problems/swap-nodes-in-pairs/submissions/495209174/
思路:①自行创建头节点②循环判断条件应为p.next!=null && p.next.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 swapPairs(ListNode head) {
if (head == null) {
return null;
}
ListNode fakeHead = new ListNode();
fakeHead.next = head;
ListNode begin = fakeHead;
ListNode p = fakeHead;
ListNode q;
while (p.next != null && p.next.next != null) {
q = p.next.next;
p.next.next=q.next;
q.next = p.next;
p.next = q;
p=p.next.next;
}
return fakeHead.next;
}
}
------------------------分割线-------------------------
160.链表相交https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/
思路：先求出两链表长度，两链表如有相交节点，一定位于短链表部分，因此长链表较长部分不做研究，从短链表头节点相应位置开始循环判断节点是否相同。
/**
* 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) {
int length_a = 0;
int length_b = 0;
ListNode p = headA;
while (p != null) {
length_a++;
p = p.next;
}
p = headB;
while (p != null) {
length_b++;
p = p.next;
}
p = headA;
ListNode q = headB;
int subValue = length_a - length_b;
if (subValue >= 0) {
p = headA;
int i = 0;
while (i < subValue) {
i++;
p = p.next;
}
} else {
subValue = -subValue;
int i = 0;
while (i < subValue) {
i++;
q = q.next;
}
}
while (p != null) {
if (p == q) {
return p;
}
p = p.next;
q = q.next;
}
return null;
}
}
-----------------------分割线-------------------------
142.环形链表IIhttps://leetcode.cn/problems/linked-list-cycle-ii/description/
思路：
/**
* 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) {
if (head == null) {
return null;
}
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
ListNode index1 = head;
ListNode index2 = slow;
while (index1 != index2) {
index1 = index1.next;
index2 = index2.next;
}
return index1;
}
}
return null;
}
}