亲宝软件园·资讯

展开

[LeetCode] 24. Swap Nodes in Pairs

wengle 人气:0

1. 原题链接:https://leetcode.com/problems/swap-nodes-in-pairs/

2. 解题思路

  1. 利用哑节点将边界case转化为一般case,比如head为NULL或者链表只有一个节点的情况都可以被转化
  2. 正常情况下,依次创建三个指针:prev,p,q,它们之间的关系是:p = prev->next,q = p->next

3. 迭代算法

  1. 创建哑节点,创建三个指针:prev,p,q
  2. 循环遍历链表,循环的判断条件是:p 和 q 都不等于NULL,循环的步长是每次向前移动两个节点
  3. 循环体执行两个节点的交换

4. 递归算法

  1. 首先,明确递归函数的功能:输入一个链表,对该链表进行两两节点交换的操作,返回交换之后的链表头节点
  2. 递归函数的结束条件:链表为NULL或者链表只有一个节点
  3. 递归函数体的主要内容:涉及到交换,所以需要保存当前两个节点;根据函数对子链表操作之后返回的结果,对当前两个节点进行交换(PS:可以理解为后序遍历,先处理子问题,子问题处理完之后,再对当前状态进行操作)

5. 实现

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
迭代版本
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode dummy(-1);
        dummy.next = head;
        
        ListNode *prev = &dummy;
        for(ListNode *p = prev->next; p != NULL && p->next != NULL; p = prev->next){
            ListNode *q = p->next;
            //swap p and q
            p->next = q->next;
            q->next = p;
            prev->next = q;
            prev = p; //注意更新prev指针
        }
        return dummy.next;
    }
};
递归版本
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        //递归结束条件
        if(head == NULL || head->next == NULL) return head;
        
        ListNode *new_head = head->next; //保存当前两个节点:head、new_head
        ListNode *n = swapPairs(head->next->next); //处理子问题
        //处理当前状态
        head->next = n;
        new_head->next = head;
        return new_head;
    }
};

加载全部内容

相关教程
猜你喜欢
用户评论