Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Swap Nodes in Pairs

Leetcode algorithms 第 24 题:Swap Nodes in Pairs。

题目

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

解答

链表操作,交换相邻元素。根据定义的操作直接进行。首先0个或1个元素的链表直接返回,否则两个两个遍历链表,再记录这两个节点的下两个节点,修改节点指针,然后再继续遍历下两个节点。

注意指针修改时NULL的情况,同时先保存新的头结点用来返回,因为后面指针修改后已经找不到新的头结点了。

具体代码如下:

/**
 * 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; //0个或1个元素直接返回
        
        ListNode *ans = head->next; //保存新的头结点
        
        ListNode *p1 = head, *p2 = head->next;
        while (p1 != NULL && p2 != NULL)
        {
            ListNode *t1 = p2->next, *t2 = t1 ? t1->next : NULL;
            p1->next = t2 ? t2 : t1, p2->next = p1; //注意t2为空时p1->next应为t1
            p1 = t1, p2 = t2;
        }
        return ans;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论