leetcode第23题--Swap Nodes in Pairs

Problem：

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

本题要我们通过节点的操作来两两置换，而不是通过修改val的值。这题主要就是考察对链表指来指去，最后指向哪里是否清楚。应该要这样考虑，对于 1 2 3 4，先设置一个头指向这个表，假设为0，则0指向1，现在我们想要的结果是0指向2指向1指向3指向4.一步一步来，先将2的next赋值给1的next，然后把1赋值给2的next，这样就有了 2指向1指向3.（如果先把1直接赋值给2的next，那么这是3就被1覆盖了，找不到3了，所以不能这样做）。我们已经有了2指向1指向3指向4，因为0指向的还是1，没改，所以这个时候要将0指向2了，那么就有了0指向2指向1指向3指向4，还没有结束，因为3和4还没有置换。同理，这个时候要先把4的next给3，再把3给4的next。这时候是不是就完了呢，不是的，因为1指向的还是3，所以还需要将4给1的next（这个通过代码中的bef（就是before的意思）来实现，每次把bef赋值为已经置换好的第二个，再把下一个置换好的头赋值给bef的next，就把整个串好了。因为我们的头是0，所以最后返回0的next指针才是答案。

代码如下：

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

class Solution {

public:

ListNode *swapPairs(ListNode *head)

{

    if(!head || !(head -> next))

    {

        return head;

    }

    ListNode *tmp = new ListNode();

    ListNode *ans = tmp;

    ListNode *bef = ans; // 用来保证将ans指向下一个二元组

    tmp -> next = head;

    tmp = tmp -> next;

    while(tmp && (tmp -> next))

    {

        ListNode *m = tmp;

        ListNode *nn = tmp -> next;

        tmp = tmp -> next;

        m -> next = nn -> next;// 例如 1 2 3，先把1指向3，再把2指向1，这样的话就是2 -> 1 -> 3

        tmp -> next =m;

        bef -> next = tmp; // bef的下一个要指向下一个二元组的第一个

        tmp = m -> next;

        bef = m;// 更新bef为转换好的二元组的后一个，为了使得和下一个二元组连接

    }

    return ans -> next; // ans 的第一个为零，next开始才是所要的

}

};

我在return上面加一个delete ans，居然还是accept。这题规模小所以new的不delete可以。如果我想要delete呢。应该如何？

巴特西

leetcode第23题--Swap Nodes in Pairs

最新文章

热门文章