leetcode 24. Swap Nodes in Pairs

ゞ浴缸里的玫瑰 2022-06-09 08:09 110阅读 0赞

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.

这道题考察的是两个节点的交换，这里是指的是指针的交换，而不是值的交换，注意指针即可。

需要注意的地方是：**设置head头结点，原因是要对第一队的交换做特殊处理，所以才添加一个head头节点。**

代码如下：

/* class ListNode {
          int val;
          ListNode next;
          ListNode(int x) { val = x; }
      }*/
    
    /*
     * 设置head结点，两两交换
     * 
     * 设置head的原因是：考虑到第一对结点的交换，
     * 所以设置head结点，一遍统一处理
     * 
     * */
    public class Solution 
    {
         public ListNode swapPairs(ListNode head) 
         {
             if(head==null || head.next==null)
                 return head;
    
             ListNode headListNode=new ListNode(-1);
             headListNode.next=head;
             ListNode fa=headListNode,now=fa.next,nextNow=now.next;
             while(now!=null && nextNow!=null)
             {
                 now.next=nextNow.next;
                 nextNow.next=now;
                 fa.next=nextNow;
    
                 fa=now;
                 now=fa.next;
                 nextNow=now!=null? now.next : null;
             }   
             return headListNode.next;
         }
    
    
    }

下面是C++代码，就是指针交换即可，

代码如下：

#include <iostream>
    using namespace std;
    
    /*
    struct ListNode
    {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
    };
    
    */
    
    class Solution
    {
    public:
        ListNode* swapPairs(ListNode* head) 
        {
            if (head == NULL || head->next == NULL)
                return head;
    
            ListNode* newHead = new ListNode(-1);
            newHead->next = head;
            ListNode* fa = newHead;
            ListNode* now = fa->next;
            ListNode* next = now->next;
    
            while (now != NULL && next != NULL)
            {
                ListNode* tmp = next->next;
                next->next = now;
                fa->next = next;
                now->next = tmp;
    
                fa = now;
                now = fa->next;
                next = now == NULL ? NULL : now->next;
            }
            return newHead->next;
        }
    };