LeetCode-中等-24-两两交换链表中的节点(C)

题目

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

示例 1:

输入:head = [1,2,3,4]
输出:[2,1,4,3]
示例 2:

输入:head = []
输出:[]
示例 3:

输入:head = [1]
输出:[1]
 

提示:

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/swap-nodes-in-pairs
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

首先要确定返回链表的头结点:
如果是空链表,或是只有一个结点,那么直接返回头结点即可。
如果有至少两个结点,则将头结点resultHead设置为第二个结点,因为两两交换后,第二个结点会成为头结点。

之后要设置一个临时结点,作为交换的媒介,
交换操作都在head结点上进行。

因为第一次交换时,这两个结点前没有结点,而后续的结点对前都有结点,需要设置前面结点的next指针,因此,交换需要分为两个部分,前两个结点,和其他结点。

前两个结点的交换方式如下:
临时结点存储第三个结点的指针,即tempNode = head->next->next;
第二个结点的next结点设置为头结点,即head->next->next = head;
第一个结点的next结点设置为第三个结点(临时结点),即head->next = tempNode;
交换完成,结点顺序为:2->1->3->4->…

之后判断head结点后的第二个结点是否存在,如果存在则需要对后面两个结点进行交换,并且还需修改head结点的next结点,操作如下:
为了方便理解,第二部分的交换以例子来讲解:

经过上一轮交换,
1->2->3->4->5->6已经被交换成为
2->1->3->4->5->6,head为1
第二轮交换循环中的五行代码功能如下所示:

此时需要先保存下3的地址
再将1->next设置为4,此时为2->1->4->5->6
再将3->next设置为5,此时2->1->4->5->6以及3->5->6
再将4->next设置为3,此时2->1->4->3->5->6,
最后,将head结点由1切换至3,以便循环中的下一轮交换。

代码

struct ListNode* swapPairs(struct ListNode* head){
    struct ListNode *resultHead = head;
    struct ListNode *tempNode;

    if(!head || !head->next) return head;
    else if(resultHead->next) {
        resultHead = resultHead->next;
        tempNode = head->next->next;
        head->next->next = head;
        head->next = tempNode;
    }
    while(head && head->next && head->next->next){
        tempNode = head->next;
        head->next = head->next->next;
        tempNode->next = head->next->next;
        head->next->next = tempNode;
        head = head->next->next;
    }
    return resultHead;
}

You may also like...

发表评论

邮箱地址不会被公开。 必填项已用*标注