【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的方式搞
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论