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

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

程序员文章站 2022-06-07 10:50:13
...

LeetCode 24 Medium

解题思路:
  • 设置头节点headPoint 统一处理各种边界问题
  • 设置pre指针指向要交换的节点的前驱,设置tmp指针指向和当前节点(current指针)进行交换,并将当前节点的next记录到node指针中
  • 两两交换,直到current或者current -->next != NULL跳出循环,返回headPoint的next
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)
结果:

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

代码
/**
 * 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) {
        if(head == NULL || head->next == NULL){
            return head;
        }
        ListNode* headPoint = (ListNode *)malloc(sizeof(ListNode));
        headPoint->next = head;
        ListNode* current = headPoint -> next;
        ListNode* tmp;
        ListNode* node;
        ListNode* swapNode;
        ListNode* pre=headPoint;
        while(current != NULL && current->next != NULL){
            tmp = current->next;
            node = tmp->next;
            pre->next = tmp;
            tmp->next = current;
            current->next = node;
            pre = current;
            current = current->next;
        }
        return headPoint->next;
    }
};