首页 > 其他 > 详细

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

时间:2020-08-13 14:08:37      阅读:46      评论:0      收藏:0      [点我收藏+]

题目

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

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

题目来源


分析

我第一个想到的思路不是递归而是迭代,但还是觉得递归比较简单。

递归:首先要先想出递归公式,根据题意是要交换相邻的节点。

first->next = swapPairs(second->next);
second->next = first;
1、第一个节点的next指针要指向第二个节点的下一个节点。
2、第二个节点的next指针要指向第一个节点。
1和2的顺序不能换,为啥?因为先执行2,second->next就会丢失,这样1也会执行错误

返回值,因为节点两两交换,自然应当返回交换之后的头结点。

递归出口
if( NULL == head || NULL == head->next )
{
return head;
}

这样,问题也就解决了。


代码实现

递归

struct ListNode* swapPairs(struct ListNode* head){
    if( NULL == head || NULL == head->next )
    {
        return head;
    }

    struct ListNode *first = head;
    struct ListNode *second = head->next;

    first->next = swapPairs(second->next);
    second->next = first;

    return second;
}

迭代

struct ListNode* swapPairs(struct ListNode* head){
    //head为NULL的情况
    if( NULL == head ) return head;
    struct ListNode *temp;
    struct ListNode *p,*q,*old;
    old = p = head; //指向头结点
    q = head->next; //指向头结点的下一个节点

    while( q != NULL && p != NULL )
    {
        temp = q;
        p->next = q->next;/*节点1指向节点3*/
        q->next = p;/*节点2指向节点1*/

        if( p==head )
        {
            head = temp;
        }
        else
        {
            old->next = temp;
        }

        old = p;
        //指向下一段要交换的节点
        p = p->next;
        if( p == NULL )/*若p=NULL,q在p后面一定是NULL*/
        {
            q = NULL;
        }
        else
        {
            q = p->next;
        }
    }
    
    return head;
}

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

原文:https://www.cnblogs.com/modesty-boy/p/13494476.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!