脚本宝典收集整理的这篇文章主要介绍了

【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群277859234一起讨论学习。如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典网站推荐给程序员好友。 本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。

80%的人都看过