c/c++ leetcode 二二交换链表节点

题目描述:

难度中等574

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

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

示例:

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

解法一:迭代(最优解)(C语言)

这是借鉴这位老哥的,他的思想很好,不好意思没有找到他的链接,这道题是我半个月前做的一道题,回顾了以前刷的题是很有必要的,老哥,要是看到的话说一声,我加上.

//分割成链表长度为K的链表节点 用temp保存k个链表节点后的节点 将k个链表节点后的next 置为NULL 返回temp//如果链表长度不够k长,则返回头结点struct ListNode* split(struct ListNode* head,int k ){    struct ListNode* temp = head;    if(!head) return head;    while(head&& --k){        head = head -> next;      if(head) {        temp = head -> next;        head ->next = NULL;        return temp ;    }    return temp;}//翻转链表struct ListNode* reversion(struct ListNode* head) {    if (!head || !(head -> next)) return head;        struct ListNode* pre = NULL;    struct ListNode* last = NULL,* temp = head;    while (head -> next) {        last = head -> next;        head -> next = pre;        pre = head;        head = last;    }        head -> next = pre;        return head;}    struct ListNode* swapPairs(struct ListNode* head){    if(!head) return head;    struct ListNode bummy,*p,*temp = head;    //哑结点    bummy.next = head;    p = &bummy;    while(temp){        struct ListNode* ret = split(temp,2);        //链表长度不够2时        if(ret == temp) break;        p ->next = reversion(head);        head ->next = ret;        p = head;        temp = ret;        head =ret;    }    return bummy.next;}

时空复杂度分析:

这位老哥没有做时空复杂度分析,我来班门弄斧一下,

时间复杂度:也就是翻转整个链表的时间复杂度为O(N);N 是链表的长度

空间复杂度:使用了常量的空间为O(1);

解法二: 递归(c++语言)

你只需要理解递归第一层逻辑就可以了不要人肉递归

ListNode* swapPairs(ListNode* head) {        if (!head || !(head -> next)) return head;		//newHead 保存第二个节点        ListNode *newHead = head -> next ;        //last 保存第三个节点 也是下一层的头结点        ListNode *last = newHead -> next;		        //让第二个节点的next 指向 第一个节点        //第一个节点和第二个节点就形成了环  第一个节点 的next同样指向第二个节点        newHead -> next = head;		//让原第一个节点 的next 链接返回的值        head -> next = swapPairs(last);        //返回第二个节点作为头结点        return newHead;    }