[LeetCode] 24. Swap Nodes in Pairs 成对交换节点

2021年09月15日 阅读数:1
这篇文章主要向大家介绍[LeetCode] 24. Swap Nodes in Pairs 成对交换节点,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

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

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.java

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.node

给定一个链表,每两个节点为一组交换位置。只使用常量空间,不能修改链表的值,只能修改链表的指针。python

题目自己不难,但要操做不少指针,容易弄错。post

解法1: 迭代。新建一个dummy节点,使用三个节点指针。url

解法2: 递归spa

Java:指针

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
  public static ListNode swapPairs(ListNode head) {
    if (head == null) {
      return null;
    }

    ListNode dummyHead = new ListNode(0);
    dummyHead.next = head;
    ListNode r = dummyHead;
    while (r != null && r.next != null && r.next.next != null) {
      ListNode p = r.next.next;
      ListNode q = r.next;
      ListNode next = p.next;
      p.next = q;
      q.next = next;
      r.next = p;
      p = q.next == null ? null : q.next.next;
      q = q.next;
      r = r.next.next;
    }

    return dummyHead.next;
  }
}  

Python: Iterationcode

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
    
    def __repr__(self):
        if self:
            return "{} -> {}".format(self.val, self.next)

class Solution:
    # @param a ListNode
    # @return a ListNode
    def swapPairs(self, head):
        dummy = ListNode(0)
        dummy.next = head
        current = dummy
        while current.next and current.next.next:
            next_one, next_two, next_three = current.next, current.next.next, current.next.next.next
            current.next = next_two
            next_two.next = next_one
            next_one.next = next_three
            current = next_one
        return dummy.next

C++: Iterationorm

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode *dummy = new ListNode(-1), *pre = dummy;
        dummy->next = head;
        while (pre->next && pre->next->next) {
            ListNode *t = pre->next->next;
            pre->next->next = t->next;
            t->next = pre->next;
            pre->next = t;
            pre = t->next;
        }
        return dummy->next;
    }
};

C++: Recursion

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode *t = head->next;
        head->next = swapPairs(head->next->next);
        t->next = head;
        return t;
    }
}; 

 

All LeetCode Questions List 题目汇总