题解 | #两两交换链表的节点#

两两交换链表的节点

题目描述 给你一个链表，请你两两交换相邻节点，你需要真正交换节点本身，而不是修改节点的值。

方法一：直接法

解题思路

对于本题，采用直接法进行求解，即两两交换相邻节点即可。

解题代码

class Solution {
public:
    ListNode* swapLinkedPair(ListNode* head)
    {
        if(head==nullptr||head->next==nullptr)
        {
            return head;
        }
        ListNode* p=head,*q=head->next,*t;//初始化
        ListNode* h=q;
        while(p&&q)
        {//循环
            t=q->next;//交换操作
            q->next=p;
            if(t&&t->next)
                p->next=t->next;
            else
                p->next=t;
            p=t;
            if(t)
            {
                q=t->next;
            }
        }
        return h;
    }
};

复杂度分析

时间复杂度：一次遍历，因此时间复杂度为$O(n)O(n)$。

空间复杂度：使用常数级内存地址空间，因此空间复杂度为$O(1)O(1)$。

方法二：Java方法

解题思路

思路同方法一，使用Java编程。

解题代码

import java.util.*;

public class Solution {
    public ListNode swapLinkedPair (ListNode head)
    {
        if(head==null||head.next==null)
        {
            return head;
        }
        ListNode p=head,q=head.next,t;//初始化
        ListNode h=q;
        while(p!=null&&q!=null)
        {//循环
            t=q.next;//交换操作
            q.next=p;
            if(t!=null&&t.next!=null)
                p.next=t.next;
            else
                p.next=t;
            p=t;
            if(t!=null)
            {
                q=t.next;
            }
        }
        return h;
    }
}

复杂度分析

时间复杂度：一次遍历，因此时间复杂度为$O(n)O(n)$。

空间复杂度：使用常数级内存地址空间，因此空间复杂度为$O(1)O(1)$。