LeetCode日记–24. Swap Nodes in Pairs

发布于 2020-10-13  115 次阅读


碎碎念:昨儿新班长请全班喝奶茶,半夜十二点喝了杯奶茶,搞得全宿舍两点多才睡,难受死了。

题目如下:

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

You may not modify the values in the list's nodes. Only nodes itself may be changed.

Example 1:

Input: head = [1,2,3,4]
Output: [2,1,4,3]

Example2:

Input: head = []
Output: []

Example3:

Input: head = [1]
Output: [1]

思路:

这题递归的话其实没什么好思路的,就是节点的调换。但是,遍历的节点应该在当前节点的前面,这样遍历的时候比较方便,而且边界问题比较少。即每次判定tmep.next 和 temp.next.next存在后再移动要交换的节点的指针。

我自己就犯了这个错误,导致debug了半天。

我的代码如下:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null)
            return head;
        ListNode newFirstNode =  head;
        ListNode firstNode = head;
        ListNode secondNode = head.next;
        head = secondNode;
        while(newFirstNode!=null){
            newFirstNode = newFirstNode.next.next;
            if(secondNode==null)
                break;
            else
                firstNode.next = secondNode.next;
            secondNode.next = newFirstNode;
            if(newFirstNode==null)
                break;
            firstNode = newFirstNode;
            secondNode = newFirstNode.next;
        }
        return head;
    }
}

添加了一个哑节点并改进了temp的位置后代码如下:

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        while (temp.next != null && temp.next.next != null) {
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            temp = node1;
        }
        return dummyHead.next;
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/swap-nodes-in-pairs/solution/liang-liang-jiao-huan-lian-biao-zhong-de-jie-di-91/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

递归实现如下:

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

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/swap-nodes-in-pairs/solution/liang-liang-jiao-huan-lian-biao-zhong-de-jie-di-91/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

递归的终止条件就是当前节点或者下一个节点为空,每次递归进去就是两个节点进行操作。head代表之前两两之中的头,newhead代表两两之间的新头。每次递归后的新头返回给之前的head作为其next。


你好哇!欢迎来到雷公马碎碎念的地方:)