题目描述

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

示例

给定 1->2->3->4, 你应该返回 2->1->4->3.

说明

你的算法只能使用常数的额外空间。 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

解题思路

利用递归的思想，依次交换链表中的节点对。具体对于每个节点来说： 1.若该节点为NULL，则直接返回NULL 2.若该节点的下一个节点为NULL，则直接返回该节点 3.交换该节点与下一个节点，利用辅助指针记录该节点的下一个节点，并递归的交换接下来的节点对

代码展示

/** Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* swapPairs(ListNode* head) { if(!head) return NULL; if(!head->next) return head; ListNode* temp=head->next; head->next=swapPairs(temp->next); temp->next=head; return temp; } }; /** 非递归代码 * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode swapPairs(ListNode head) { if(head == null) return head; ListNode cur = head; ListNode prev = cur; // 连接每对节点 if(cur.next != null) head = cur.next; while(cur != null && cur.next != null){ prev.next = cur.next; ListNode next = cur.next.next; // next用来保存下一对节点的开始节点 cur.next.next = cur; cur.next = next; prev = cur; // prev指向每一对反转之后节点的第二个节点 cur = next; // cur指向每一对节点的第一个节点 } return head; } }