24.Swap-Nodes-in-Pairs

24. 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;
}
}