链表反转&交换链表结点

leetcode链表反转链接

要求摘要：

反转一个单链表

输入: 1->2->3->4->5->NULL

输出: 5->4->3->2->1->NULL

做法是考虑把链表中结点的next指向它的上一个结点，以此来进行反转。

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     struct ListNode *next;

 * };

 */

struct ListNode* reverseList(struct ListNode* head){

    if(head==NULL)

        return NULL;

    struct ListNode* pre=NULL;

    struct ListNode* p=head;

    struct ListNode* h=NULL;

    while(p)

    {

        h=p;          //h不断变化，最终为反转链表的头结点

        struct ListNode* tmp=p->next; //tmp不断指向下一个结点，用于遍历链表

        p->next=pre;    //将p结点的指针域由指向p的下一个结点，转而指向p的上一个结点

        pre=p;     //将pre设为当前结点，取下一个结点时，pre即为下一个结点的上一个结点

        p=tmp;             //即p=p->next，不断取下一个结点

    }

两两交换链表中的节点

要求摘要：

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

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

示例：给定 1->2->3->4, 你应该返回 2->1->4->3。

做法：

每一次操作需要知道三个结点，当前结点的上一个结点tmp，当前结点pre，当前结点的下一个结点tail。可以看做每三个结点一组。其中，本组当前结点pre的上一个结点tmp，是上一组的最后一个节点tail，然后对本组的pre和tail进行交换操作。

移动到下一个结点或者说移动到下一组：

具体结点交换操作步骤示意图：

完整代码：

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     struct ListNode *next;

 * };

 */

truct ListNode* swapPairs(struct ListNode* head){

	//如果为空返回NULL；只有一个节点原样返回

	if(head==NULL)

		return NULL;

	if(head->next==NULL)

		return head;

	struct ListNode* tmp=NULL;  //作用是保存一次循环后的末位节点

	struct ListNode* pre=head;

	struct ListNode* tail=NULL;

	tail=head->next; //先进行一次结点交换操作是为了确定头结点

    //结点交换

	pre->next=tail->next;

	tail->next=pre;

	head=tail;

	tmp=pre;  //保存末位节点

	pre=pre->next; //当前结点后移，便于下一次操作

	if(pre==NULL || pre->next==NULL) //如果链表只有两个或三个结点，返回该链表

		return head;

	while(pre && pre->next)

	{

		tail=pre->next;

		//结点交换

		pre->next=tail->next;

		tail->next=pre;

		tmp->next=tail;

		tmp=pre; //保存末位节点

		pre=pre->next;

	}

	return head;

}

另，附上一个很简洁的代码：

ListNode *swapPairs(ListNode *head) {

        if (!head) return NULL;

        if (!head->next) return head;

        ListNode *temp = head->next;

        head->next = swapPairs(temp->next);

        temp->next = head;

        return temp;

    }

这段代码原帖：https://blog.csdn.net/stay_the_course/article/details/88729356

巴特西

链表反转&交换链表结点

leetcode链表反转链接

两两交换链表中的节点

最新文章

热门文章