本文共 1330 字，大约阅读时间需要 4 分钟。

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.

其实关于链表的算法题思路都很easy，但是细节真的会崩溃，不管是反转链表，还是合并链表吗，还是删除指定节点，一定要小心临界条件的判断。就拿本题为例子吧，就是反转链表一个变形，它要求的是对相邻一对节点进行交换，交换的结束的条件怎么判断，（也就是怎么结束循环），如果交换的是头结点怎么处理，真心要小心小心再小心。上代码：

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     struct ListNode *next; * }; */struct ListNode* swapPairs(struct ListNode* head) {    struct ListNode* p = head;    struct ListNode* pPre = NULL;    struct ListNode* prePre = NULL;    struct ListNode* pNext;    while(p && p->next){        pPre = p;        p=p->next;        pNext = p->next;        if(pPre == head)          head = p;        if(prePre)           prePre->next = p;        pPre->next = pNext;        p->next = pPre;        prePre = pPre;        p = pNext;    }    return head;}

这里再说一个稍有难度的一个题，也是跟链表有关，不过这道题考察的重点是写一个堆排序的算法。

leetcode Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

别看题目就一句话描述，殊不知，越简短的描述越是个坑。

其实不想自己写堆排序直接用C++提供的make_heap(), push_heap(), pop_heap(), sort_heap()也能解决，但是C++提供的是大顶堆，而本题是要用到小顶堆。之前刷的时候对堆排序还不太了解，参考了： 这个博客讲的很详细。

转载地址：http://fjtsi.baihongyu.com/