LeetCode 24. 两两交换链表中的节点

原题链接 本题两种思路，递归和非递归 我使用的是递归结构，运行的结果很惨，时间和内存都是5%。思路比较简单

递归思路：

从前往后处理链表，声明指针 ListNode *p，*q，p在前，q在后；将p和q的位置互换；p要先指向q->next，q后面的节点递归处理；递归推出条件为链表中少于两个节点；

给出代码：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode *p, *q, *k; if( head == NULL) return nullptr; p = head; q = head->next; k = head->next; if(!(p&&q)) return p; //当未剩下的链表只有一个节点或者没有节点的时候直接返回 p->next = swapPairs(q->next); k->next = p; return q; } };

非递归的做法是增加一个头节点，迭代交换 递归结构增加了时间和空间的开销。尽量减少递归的使用。