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呢。应该如何?

04-24 05:52