LeetCode 24. 两两交换链表中的节点
思路：一开始思路方向错误了，想着需要翻转列表，卡了好久，还导致链表内成环。其实画图看每个节点的next是哪个，分步骤走会简单很多。
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null)
return head;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode cur = dummy;
while(cur != null && cur.next != null && cur.next.next != null){
ListNode temp1 = cur.next;
ListNode temp2 = cur.next.next;
ListNode temp3 = cur.next.next.next;
cur.next = temp2;
temp2.next = temp1;
temp1.next = temp3;
cur = temp1;
}
return dummy.next;
}
}class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null)
return head;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy;
ListNode cur = head;
while(cur != null && cur.next != null){
ListNode temp = cur.next.next;
prev.next = cur.next;
prev.next.next = cur;
cur.next = temp;
prev = cur;
cur = temp;
}
return dummy.next;
}
}?LeetCode?19.删除链表的倒数第N个节点
使用两趟扫描实现，第一趟求链表长度，第二趟才进行删除。
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
int sz = 0;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode cur = head;
while(cur != null){
sz++;
cur = cur.next;
}
//System.out.println("sz: " + sz);
cur = dummy;
if(n == sz)
return head.next;
for(int i = 0; i < sz - n; i++){
cur = cur.next;
}
cur.next = cur.next.next;
return dummy.next;
}
}通过快慢指针实现一趟删除：
- fast首先走n + 1步 ，同时移动的时候slow才能指向删除节点的上一个节点
- fast和slow同时移动，直到fast指向末尾
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast = head;
// fast先走(n+1)步，那样等fast到null的时候，slow就到要删除的节点的上一个节点
while(n-- > 0){
fast = fast.next;
}
if(fast == null)
return head.next;
fast = fast.next;
ListNode slow = head;
while(fast != null){
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return head;
}
}?LeetCode?面试题 02.07. 链表相交
重点：交点不是数值相等，而是指针相等！
思路：
- 考虑构建两个节点指针?
A??,?B?分别指向两链表头节点?headA?,?headB - 指针?
A?先遍历完链表?headA?，再开始遍历链表?headB - 指针?
B?先遍历完链表?headB?，再开始遍历链表?headA - 若两链表有公共尾部：指针?
A?,?B?同时指向「第一个公共节点」node - 若两链表无：指针?
A?,?B?同时指向?null
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null){
return null;
}
ListNode curA = headA;
ListNode curB = headB;
Boolean isLinked = false;
while(curA != null || isLinked == false){
if(curA == curB)
break;
if(curA.next == null && isLinked == false){
isLinked = true;
curA = headB;
}else{
curA = curA.next;
}
if(curB.next == null){
curB = headA;
}else{
curB = curB.next;
}
}
return curA;
}
}?LeetCode?环形链表II?
思路：设两指针?fast，slow?指向链表头部?head，fast?每轮走2步，slow?每轮走1步
根据：
-
f=2s? (快指针每次2步，路程刚好2倍）
-
f = s + nb (相遇时，刚好多走了n圈）
推出：s = nb
从head结点走到入环点需要走 ： a + nb， 而slow已经走了nb，那么slow再走a步就是入环点了。
如何知道slow刚好走了a步？ 从head开始，和slow指针一起走，相遇时刚好就是a步
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null || head.next == null)
return null;
ListNode fast = head;
ListNode slow = head;
do{
if(fast == null || fast.next == null)
return null;
fast = fast.next.next;
slow = slow.next;
}while(fast != slow);
fast = head;
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
return fast;
}
}