LeetCode 24. Swap Nodes in Pairs

LeetCode 24. Swap Nodes in Pairs

DescriptionExampleCodeConclusion

Description

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.

Code

java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode swapPairs(ListNode head) { int i = 0; ListNode pNode = head; LinkedList<ListNode> odd = new LinkedList<ListNode>(); LinkedList<ListNode> even = new LinkedList<ListNode>(); while(pNode != null) { if(i % 2 == 1) { odd.add(pNode); } else { even.add(pNode); } i++; pNode = pNode.next; } ListNode nHead = new ListNode(0); pNode = nHead; while(!odd.isEmpty() || !even.isEmpty()) { if(!odd.isEmpty()) { pNode.next = odd.pop(); pNode = pNode.next; } if(!even.isEmpty()) { pNode.next = even.pop(); pNode = pNode.next; } } pNode.next = null; return nHead.next; } } Others’ SolutionRecursionjava public class Solution { public ListNode swapPairs(ListNode head) { if ((head == null)||(head.next == null)) return head; ListNode n = head.next; head.next = swapPairs(head.next.next); n.next = head; return n; } }

Conclusion

评论区递归版本牛逼