LeetCode 24 Swap Nodes in Pairs(交换序列中的结点)(Linked List)

  1. 云栖社区>
  2. 博客>
  3. 正文

LeetCode 24 Swap Nodes in Pairs(交换序列中的结点)(Linked List)

nomasp 2015-11-12 18:43:57 浏览390
展开阅读全文
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/49803287

翻译

给定一个链表,调换每两个相邻节点,并返回其头部。

例如,
给定 1->2->3->4, 你应该返回的链表是 2->1->4->3。

你的算法必须使用唯一不变的空间。

你也不能修改列表中的值,只有节点本身是可以改变的。

原文

Give 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.

分析

先来看看如何交换两个节点吧~

也以“1 -> 2 -> 3 -> 4”作为例子,交换前两个即可。

错误示例1:

ListNode tmp = head.next;
tmp.next = head;
head.next = tmp;

它将以此变成:

tmp -> head -> tmp -> head -> tmp
2 -> 1 -> 2 -> 1 -> 2 -> 1 ...

正确示例:

ListNode tmp = head.next;
// become : 2 -> 3 -> 4
head.next = tmp.next;
// become : 1 -> 3 -> 4
tmp.next = head;
// become : 2 -> 1 -> 3 -> 4

如何要对后续的元素也进行swap,只用递归替换掉tmp.next即可。

ListNode* temp = head->next;
head->next = swapPairs(temp->next);
temp->next = head;

我们就以题目中给出的1,2,3,4作为示例,将其作为两部分

1,2 -- 3,4

或者我画个图出来更加直观吧……

这里写图片描述

主要的思想是递归,拆分成2部分:

1,将第3个节点开始的链表作为下一次递归的参数,用它去继续交换。
2,将第1个节点指向递归返回的结果,将第2个节点重新指向第1个节点,并返回它,这是新的head。

递归终止的两种情况:

1,没有节点了,返回NULL作为结束。
2,只有一个节点了,不用交换,直接返回它即可。

代码

C Plus Plus

/**
 * 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 == NULL) return NULL;
        if(head->next == NULL) return head;

        ListNode* temp = head->next;
        head->next = swapPairs(temp->next);
        temp->next = head;

        return temp;
    }
};

Java

    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode tmp = head.next;
        head.next = swapPairs(tmp.next);
        tmp.next = head;

        return tmp;
    }

网友评论

登录后评论
0/500
评论
nomasp
+ 关注