首页 > 代码库 > LeetCode Swap Nodes in Pairs

LeetCode Swap Nodes in Pairs

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

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

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

解法:可以使用递归,每次交换前两个,将剩下的链表递归,返回的是新的链表头。

 

 1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { 7  *         val = x; 8  *         next = null; 9  *     }10  * }11  */12 public class Solution {13     public ListNode swapPairs(ListNode head) {14             if (head==null || head.next==null) {15                 return head;16             }17         ListNode p = head;18         ListNode begin=null;19            ListNode temp = p;20            21            p=p.next;22            temp.next=p.next;23            p.next=temp;24            if (begin==null) {25             begin = p;26         }27             p=p.next;28             p.next=swapPairs(p.next);29             return begin;30     }31 }

 

LeetCode Swap Nodes in Pairs