交换链表节点

题目链接

https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html

思路

递归交换，注意递归退出条件

 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个节点

题目链接

https://programmercarl.com/0019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9.html

思路

快慢指针，快指针先移动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;
}

链表相交

题目链接

https://programmercarl.com/%E9%9D%A2%E8%AF%95%E9%A2%9802.07.%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4.html

思路

两个指针分别走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;

环形链表

题目链接

https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html#_142-%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8ii

思路

这个感觉属于数学分析题，代码实际不复杂。
快慢指针直到相遇，然后从链表头继续走直到相遇

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;
}