leetcode-两两交换链表中的节点之DFS+迭代

题目

递归法

这题用递归最简单，因为每两个相邻节点都可以被分割为同样的子问题：将后者指向前者，然后让前者再去指向后面两个交换后的后者

class Solution { public: ListNode* swapPairs(ListNode* head) { if(head==NULL) return NULL; return DFS(head,head->next); } ListNode* DFS(ListNode*p1, ListNode* p2) { if(p1==NULL) return NULL; if(p2==NULL) return p1; ListNode*tmp = p2->next; p2->next = p1; if(tmp==NULL) p1->next = NULL; else p1->next = DFS(tmp,tmp->next); return p2; } };

迭代法

将递归转为迭代

class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode* res = new ListNode; ListNode* tmp = res; res->next = head; while(head!=NULL && head->next!=NULL){ ListNode* first = head; ListNode* second = head->next; ListNode* third = head->next->next; second->next = first; first->next = third; tmp->next = second; tmp = first; head = third; } return res->next; } };