欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode 24.两两交换链表的结点

程序员文章站 2022-05-06 11:01:12
...

leetcode 24.两两交换链表的结点

题目描述

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

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

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

解题思路

在反转链表的基础上,对节点进行计数,每两个节点记性一次反转,需要考虑的边界情况包括:链表是否为空,链表中有奇数个节点,链表节点小于两个。

/**
 * 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* cur = head;     // 定义移动的节点
        ListNode* pre(NULL);      // 反转节点后,链表的头
        ListNode* newHead(NULL);  // 生成新的链表的头节点
        ListNode* temp;           // 每次反转,会产生一个包含两个节点的链表,定义temp用于记录生成链表的头,便于指向下一个新生成的链表
        int cnt = 0;             // 计数,每两个节点反转一次
        bool flag = false;       // 用于记录链表的长度是否超过两个
        while(cur){
            // 下面四句就是反转链表
            ListNode* pnext = cur->next;  
            cur->next = pre;
            pre = cur;
            cur = pnext;
            cnt++;  // 每遍历一个节点计数一次
            if(cnt % 2 ==0){   
                if(!flag){        // 第一次反转的两个节点处理
                    newHead = pre;   // 第一次反转后,需要记录头节点
                    temp = newHead;
                }
                else{            // 第二次后产生的反转
                    temp = temp->next;   
                    temp->next = pre;    // 此时temp->next指向的是前一次反转节点的尾部,应该指向新生成节点的头部
                    temp = temp->next;   // 把temp移动到新生成反转的头部,用于下一次的处理
                }
                flag = true;
                pre = pre->next->next;   // 这里每两次反转以后,需要把pre置为NULL
            }
        }
        // 这里如果反转的节点大于2,并且为奇数的情况
        if (pre && flag){
            temp->next->next = pre;
        }
        else if(pre && !flag){       // 节点小于2,并且不为空的情况
            newHead = pre;
        }
        return newHead;
    }
};

欢迎大家关注我的个人公众号,同样的也是和该博客账号一样,专注分享技术问题,我们一起学习进步
leetcode 24.两两交换链表的结点