欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Swap Nodes in Pairs

程序员文章站 2022-03-05 08:13:17
...

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

答案
recursion答案,很简洁,可惜只要recursion就不是O(1) space了
思路是swap current pairs, recursively swap later pairs

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head != null && head.next != null) {
            ListNode next = head.next;
            ListNode next2 = next.next;
            next.next = head;
            head.next = swapPairs(next2);
            return next;
        }
        return head;
    }
}
public class Solution {
    public static ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode first    = head;
        ListNode second   = head.next;
        ListNode previous = null, ret = second;
        while(first != null && second != null) {
            // swap first and second
            first.next = second.next;
            second.next = first;
            if(previous != null) previous.next = second;
            previous = first;
            
            first = first.next;
            if(first != null) second = first.next;
        }
        return ret;        
    }
}