24.Swap-Nodes-in-Pairs

24. Swap Nodes in Pairs

题目地址

https://leetcode.com/problems/swap-nodes-in-pairs/

题目描述

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:
Given 1->2->3->4, you should return the list as 2->1->4->3.

代码

Approach #1 Recursive Approach

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

    ListNode firstNode = head;
    ListNode secondNode = head.next;

    firstNode.next = swapPairs(secondNode.next);
    secondNode.next = firstNode;

    return secondNode;
  }
}

Approach #2 Iterative

class Solution {
  public ListNode swapPairs(ListNode head) {
    ListNode dummy = new ListNode(-1);

    dummy.next = head;
    ListNode prevNode = dummy;
    while (head != null && head.next != null) {
      ListNode firstNode = head;
      ListNode secondNode = head.next;

      prevNode.next = secondNode;
      firstNode.next = secondNode.next;
      secondNode.next = firstNode;

      prevNode = fristNode;
      head = firstNode.next;
    }

    return dummy.next;
  }
}