24.两两交换链表中的节点

第一次尝试

超时了,推测是循环的问题
仔细想想好像是更新指针的问题,这一版代码的逻辑是先将curNode指向后两位的结点,然后再把nextNode指向curNode,然后再将curNode更新为curNode->next也就是curNode的后两位,再把nextNode指向curNode->next.

这样会导致一个问题,在进入下一次循环的时候,上一次的curNode->next不会更新,比如1->2->3->4,在第一次循环结束的时候的状态为2->1->3->4,在下一次循环结束的时候就会变成一个很奇怪的状态,3->null,4->3,2->1->3.

class Solution
{
public:
    ListNode *swapPairs(ListNode *head)
    {
        ListNode *sentinelNode = new ListNode(0);
        sentinelNode->next = head;
        ListNode *temp;
        ListNode *curNode = sentinelNode->next;
        ListNode *nextNode = sentinelNode;
        if (curNode == NULL && curNode->next == NULL)
        {
            return nextNode;
        }
        while (nextNode->next != NULL)
        {
            temp = nextNode;
            curNode->next = nextNode->next;
            temp->next = curNode;
            curNode = curNode->next;
            nextNode = curNode->next;
        }
        return sentinelNode->next;
    }
};

第二次尝试

还是出现了丢节点的情况

class Solution
{
public:
    ListNode *swapPairs(ListNode *head)
    {
        ListNode *sentinelNode = new ListNode(0);
        sentinelNode->next = head;
        ListNode *temp;
        ListNode *curNode = sentinelNode;
        ListNode *nextNode;
        while (curNode->next != NULL || curNode->next->next != NULL)
        {
            nextNode = curNode->next;
            temp = nextNode->next->next;
            curNode->next = nextNode->next;//
            curNode = curNode->next;//应该是这三行出了毛病
            curNode->next = nextNode;//
            nextNode->next = temp;
        }
        return sentinelNode->next;
    }
};

第三次尝试

class Solution
{
public:
    ListNode *swapPairs(ListNode *head)
    {
        ListNode *sentinelNode = new ListNode(0);
        sentinelNode->next = head;
        ListNode *temp;
        ListNode *curNode = sentinelNode;
        ListNode *nextNode;
        while (curNode->next != NULL || curNode->next->next != NULL)
        {
            nextNode = curNode->next;
            temp = nextNode->next;
            curNode->next = temp;
            nextNode->next = temp->next;
            temp->next = nextNode;
            curNode = temp;
            nextNode = nextNode->next;
        }
        return sentinelNode->next;
    }
};

服了,居然是while循环里的符号出问题了,应该是与,脑子抽了... 不过在这一版本中,节点更新的逻辑也有问题,实际上curNode应该更新到==下一对==节点的起始位置.而且nextNode是在循环开始更新的.

最终版本

class Solution
{
public:
    ListNode *swapPairs(ListNode *head)
    {
        ListNode *sentinelNode = new ListNode(0);
        sentinelNode->next = head;
        ListNode *temp;
        ListNode *curNode = sentinelNode;
        ListNode *nextNode;
        while (curNode->next != NULL && curNode->next->next != NULL)
        {
            nextNode = curNode->next;
            temp = nextNode->next;
            curNode->next = temp;
            nextNode->next = temp->next;
            temp->next = nextNode;
            curNode = nextNode;
        }
        return sentinelNode->next;
    }
};

19.删除链表的倒数第 N 个结点

分为三种情况思考,一般情况,删除的是最后一个节点的情况和空链表的情况.

一次成功

class Solution
{
public:
    ListNode *removeNthFromEnd(ListNode *head, int n)
    {
        ListNode *sentinelNode = new ListNode(0, head);
        ListNode *curNode = sentinelNode;
        int count = 0;
        while (curNode->next != NULL)
        {
            curNode = curNode->next;
            count++;
        }
        curNode = sentinelNode;
        for (int i = 0; i < count - n; i++)
        {
            curNode = curNode->next;
        }
        curNode->next = curNode->next->next;
        return sentinelNode->next;
    }
};

面试题02 07.链表相交

class Solution
{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {

        ListNode *ANode = headA;
        ListNode *BNode = headB;
        ListNode *curNode = ANode;
        ListNode *curA;
        ListNode *curB;
        int countA = 0;
        int countB = 0;
        int sub = 0;
        while (curNode != NULL)
        {
            curNode = curNode->next;
            countA++;
        }
        curNode = headB;
        while (curNode != NULL)
        {
            curNode = curNode->next;
            countB++;
        }
        curA = headA;
        curB = headB;
        if (countB > countA)
        {
            swap(countA, countB);
            swap(curA, curB);
        }

        sub = countA - countB;

        while (sub--)
        {
            curA = curA->next;
        }

        while (curA != NULL)
        {
            if (curA == curB)
            {
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }

        return NULL;
    }
};

142.环形链表II

第一次尝试

class Solution
{
public:
    ListNode *detectCycle(ListNode *head)
    {
        ListNode *fast = head;
        ListNode *slow = head;
        while (fast != slow && fast->next != NULL)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        if (fast == slow)
        {
            ListNode *index1 = fast;
            ListNode *index2 = head;
            while (index1 != index2)
            {
                index1 = index1->next;
                index2 = index2->next;
            }
            return index1;
        }
        return NULL;
    }
};

理解的还不够深

设置快慢指针,如果有环的话,指针一定会在环内相遇,而且是在慢指针进入环内的第一圈内.
而且快指针走的路程一定是慢指针的两倍
设从起始点到进入环点路程为x,入环点到相遇点路程为y,相遇点再到入环点路程为z.
Sfast = x + n(y+z) + y;
Sslow = x + y;
且Sslow * 2 = Sfast
结合上述式子化简得到
2x + 2y = x + y + n(y + z)
x + y = n(y + z)
x = (n - 1)y + nz
x = (n - 1)y + (n - 1)z + z
x = z
所以我们令index1 = fast与slow相遇的节点
index2 = head
当index1 == index2的时候,就是进入节点的时候.

实现代码

class Solution
{
public:
    ListNode *detectCycle(ListNode *head)
    {
        ListNode *fast = head;
        ListNode *slow = head;
        while (fast != NULL && fast->next != NULL)
        {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow)
            {
                ListNode *index1 = fast;
                ListNode *index2 = head;
                while (index1 != index2)
                {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index1;
            }
        }
        return NULL;
    }
};