【两两交换链表中的节点】

2023-12-30 17:52:45

Problem: 24. 两两交换链表中的节点

文章目录

思路

把第一步的模拟过程的步骤记录下来
一共分为三个步骤

在这里插入图片描述

解题方法

创建虚拟头节点
循环什么时候结束,需要考虑问题

Q:

  1. 奇数链表结束条件?
  2. 偶数链表结束条件?
  3. 为什么结束条件是与?

A:

  • cur->next为空结束

  • cur->next->next为空结束

  • 如果是cur->next != NULL || cur->next->next != NULL
    则当链表为奇数链表时,cur->next != NULL也成立,不符合条件。(根据模拟过程,如果要改变1和2的位置,指针cur需要指向前一个位置,即dummy,同理,改变3和4位置,cur指向2,当3和4交换完毕,cur会指向4,再进行条件判断)
    在这里插入图片描述
    注意要点
    cur->next != NULLcur->next->next != NULL顺序不能错,否则会出现空指针异常
    以下是链表模拟过程
    步骤一
    在这里插入图片描述
    步骤2
    在这里插入图片描述
    步骤3
    在这里插入图片描述

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* cur = dummyHead;

        while (cur->next != NULL && cur->next->next != NULL) // 注意是与,并且顺序不能错,不然就异常
        {
            ListNode* tmp = cur->next; // 把步骤2的内容存下
            ListNode* tmp1 = cur->next->next->next; // 把步骤3的内容存下

            cur->next = cur->next->next; // 步骤1
            cur->next->next = tmp; // 步骤2
            cur->next->next->next = tmp1; // 步骤3

            cur = cur->next->next;
        }
        head = dummyHead->next;
        delete dummyHead;
        return head;
        
    }
};

文章来源:https://blog.csdn.net/Mr_robot714/article/details/135306695
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。