24. Swap Nodes in Pairs.md

24. Swap Nodes in Pairs

---

leetcode-cn Daily Challenge on October 13th, 2020.

leetcode Daily Challenge on December 24th, 2020.

---

Difficulty : Medium

Related Topics : LinkedList

---

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:

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

Example 2:

Input: head = []
Output: []

Example 3:

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

Constraints:

• The number of nodes in the list is in the range [0, 100].
• 0 <= Node.val <= 100

---

Solution

• Java
  • mine

    • Runtime: 0 ms, faster than 100.00%, Memory Usage: 37.4 MB, less than 5.50% of Java online submissions

      // O(N)time
      // O(N)space
      public ListNode swapPairs(ListNode head) {
          if (head == null || head.next == null) {
              return head;
          }
          List<ListNode> list = new ArrayList<>();
          ListNode t;
          while (head != null) {
              t = head;
              list.add(t);
              head = head.next;
          }
          for(ListNode node : list){
              node.next = null;
          }
          t = new ListNode(0);
          ListNode res = t;
          int i = 1;
          for (; i < list.size(); i += 2) {
              t.next = list.get(i);
              t = t.next;
              t.next = list.get(i - 1);
              t = t.next;
          }
          if (i == list.size()) {
              t.next = list.get(list.size() - 1);
          }
          return res.next;
      }
      

    • Runtime: 0 ms, faster than 100.00%, Memory Usage: 39.3 MB, less than 5.50% of Java online submissions

      // O(N)time
      // O(N)space
      public ListNode swapPairs(ListNode head) {
          if(head != null && head.next != null){
             ListNode next = swapPairs(head.next.next);
             ListNode res = head.next;
             head.next.next = head;
             head.next = next;
             return res;
          }else{
              return head;
          }
      }
      

---

• the most votes

• recursive Runtime: 0 ms, faster than 100.00%, Memory Usage: 37.2 MB, less than 5.50% of Java online submissions

  //O(N)time O(1)space
  public ListNode swapPairs(ListNode head) {
      if (head == null || head.next == null) return head;
      ListNode second = head.next;
      ListNode third = second.next;
  
      second.next = head;
      head.next = swapPairs(third);
  
      return second;
  }
  

• exchange Runtime: 0 ms, faster than 100.00%, Memory Usage: 37.2 MB, less than 5.50% of Java online submissions

  //O(N)time O(1)space
  public ListNode swapPairs(ListNode head) {
      ListNode dummy = new ListNode(0);
      dummy.next = head;
      ListNode current = dummy;
      while (current.next != null && current.next.next != null) {
          ListNode first = current.next;
          ListNode second = current.next.next;
          first.next = second.next;
          current.next = second;
          current.next.next = first;
          current = current.next.next;
      }
      return dummy.next;
  }
  

---