脚本宝典收集整理的这篇文章主要介绍了【leetcode】24. Swap Nodes in Pairs,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
24. Swap Nodes in Pairs
Difficulty: Medium
Given a linked list, swap every two adjacent nodes and return ITs head.
Example:
Given 1->2->3->4
, you should return the list as 2->1->4->3
.
Note:
- Your algorithm should use only constant extra space.
- You may not modify the values in the list's nodes, only nodes itself may be changed.
Solution 1
/**
* 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) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
head = dummy;
while (head->next != NULL && head->next->next != NULL) {
ListNode* n1 = head->next;
ListNode* n2 = head->next->next;
/* head->n1->n2->... => head->n2->n1->... */
head->next = n2;
n1->next = n2->next;
n2->next = n1;
/* move to next pair */
head = n1;
}
return dummy->next;
}
};
没什么好说的,就是成对的翻转即可
Solution 2
public class Solution {
/**
* @param head: a ListNode
* @return: a ListNode
*/
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode head1 = head;
ListNode head2 = head.next;
ListNode start1 = head1;
ListNode start2 = head2;
while (start2 != null && start2.next!= null) {
start1.next = start2.next;
start2.next = start2.next.next;
start1 = start1.next;
start2 = start2.next;
}
start1.next = null;
ListNode dummy = new ListNode(-1);
ListNode newStart = dummy;
while (head1!=null || head2!=null) {
if (head2 != null) {
newStart.next = head2;
head2 = head2.next;
newStart = newStart.next;
}
if (head1 != null) {
newStart.next = head1;
head1 = head1.next;
newStart = newStart.next;
}
}
return dummy.next;
}
}
模仿2个链表merge的方式搞
以上是脚本宝典为你收集整理的【leetcode】24. Swap Nodes in Pairs全部内容,希望文章能够帮你解决【leetcode】24. Swap Nodes in Pairs所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。