首页 > 代码库 > Swap Nodes in Pairs
Swap Nodes in Pairs
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.
分析: 比较简单的链表操作 需要将a->b->(b->next) 转换为b->a->(b->next)这样的形式
自己写的代码为
/** * 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 ==nullptr || head->next ==nullptr) return head; ListNode* cur = head; ListNode* curNext = cur->next; cur->next = curNext->next; curNext->next = cur; head= curNext; ListNode* prev = cur; while(prev && prev->next){ cur = prev->next; curNext = cur->next; if(curNext){ cur->next = curNext->next; curNext->next = cur; prev->next = curNext; prev = cur; }else{ cur->next =curNext; prev = nullptr; } } return head; } };
Discuss中提出的用指针的指针解决方案,稍微难一点,但很高效
ListNode* swapPairs(ListNode* head) { ListNode **pp = &head, *a, *b; while ((a = *pp) && (b = a->next)) { a->next = b->next; b->next = a; *pp = b; pp = &(a->next); } return head; }
Swap Nodes in Pairs
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。