1. 首页
  2. Leetcode经典148题

leetCode-24-Swap-Nodes-in-Pairs

题目描述(中等难度)

leetCode-24-Swap-Nodes-in-Pairs

给定一个链表,然后两两交换链表的位置。

解法一 迭代

首先为了避免单独讨论头结点的情况,一般先申请一个空结点指向头结点,然后再用一个指针来遍历整个链表。

先来看一下图示:

leetCode-24-Swap-Nodes-in-Pairs

leetCode-24-Swap-Nodes-in-Pairs

leetCode-24-Swap-Nodes-in-Pairs

leetCode-24-Swap-Nodes-in-Pairs

leetCode-24-Swap-Nodes-in-Pairs

point 是两个要交换结点前边的一个位置。

public ListNode swapPairs(ListNode head) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode point = dummy;
    while (point.next != null && point.next.next != null) { 
        ListNode swap1 = point.next;
        ListNode swap2 = point.next.next;
        point.next = swap2;
        swap1.next = swap2.next;
        swap2.next = swap1;
        point = swap1;
    }
    return dummy.next;
}

时间复杂度:O(n)。

空间复杂度:O(1)。

解法二 递归

参考这里

自己画了个参考图。

leetCode-24-Swap-Nodes-in-Pairs

leetCode-24-Swap-Nodes-in-Pairs

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

递归时间复杂度留坑。

自己开始没有想出递归的算法,每次都会被递归的简洁吸引。另外,感觉链表的一些题,只要画图打打草稿,搞清指向关系,一般不难。

作者:windliang

来源:https://windliang.cc

JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:leetCode-24-Swap-Nodes-in-Pairs

链接:https://www.javajike.com/article/3161.html

« leetCode-23-Merge-k-Sorted-Lists
leetCode-25-Reverse-Nodes-in-k-Group»

相关推荐

QR code