LeetCode24.两两交换链表

一定要注意,如果一个节点没有被其他节点指向的时候,就会丢失.所以我们在改变节点指向的时候,一定要想办法暂存住着个节点,否则原先节点之后的节点就会丢失,如图
当我们把节点0的next指向2的时候,节点1就会丢失

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode temp;
        ListNode tempNext;
        ListNode sentinel = new ListNode(205, head);
        ListNode curNode = sentinel;

        while (curNode.next != null && curNode.next.next != null) {
            temp = curNode.next.next;
            tempNext = curNode.next.next.next;
            curNode.next.next.next = curNode.next;
            curNode.next.next = tempNext;
            curNode.next = temp;
            curNode = curNode.next.next;
        }
        return sentinel.next;
    }
}

LeetCode19.删除链表的倒数第N个节

这里使用快慢指针

代码实现:

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode sentinel = new ListNode(205, head);
        ListNode firstNode = sentinel;
        ListNode lastNode = sentinel;

        for (; n > 0; n--) {
            firstNode = firstNode.next;
        }

        while (firstNode.next != null) {
            firstNode = firstNode.next;
            lastNode = lastNode.next;
        }

        lastNode.next = lastNode.next.next;
        return sentinel.next;
    }
}

LeetCode7.链表相交

思路:

代码实现:

ublic class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int countA = 0;
        int countB = 0;
        int count = 0;
        ListNode tempNode;
        int temp;

        while (headA != null) {
            headA = headA.next;
            countA++;
        }
        while (headB != null) {
            headB = headB.next;
            countB++;
        }

        if (countB > countA) {
            temp = countA;
            countA = countB;
            countB = temp;

            tempNode = curA;
            curA = curB;
            curB = tempNode;

        }

        int n = countA - countB;

        for (; n > 0; n--) {
            curA = curA.next;
        }

        while (curA != null) {
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;

    }
}

LeetCode142.环形链表

下面是一个环形链表示意图

解题思路还是用快慢指针,设定快指针一次前进两个节点,慢指针一次前进一个节点,这样快慢指针就能在==环内相交==(且是在一圈以内相交)

关于环内相交的示意图:
假设快慢指针都在起点,但是快指针稍微比慢指针靠前一点点点点,慢指针跑半圈的时候,快指针已经跑了一圈了,慢指针跑完一圈的时候,快指针已经跑了两圈了,所以肯定能在慢指针进入环的第一圈追上慢指针

下面是求进入环的点的方法.
我们利用相同时间内,快指针前进的节点数一定是慢指针的两倍
请看如图的计算过程

代码实现:

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fastNode = head;
        ListNode slowNode = head;

        while (fastNode != null && fastNode.next != null) {
            fastNode = fastNode.next.next;
            slowNode = slowNode.next;
            if (fastNode == slowNode) {
                ListNode index1 = head;
                ListNode index2 = fastNode;
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            } 
        }
        return null;
    }
}