链表--交换链表相邻的两个元素

交换链表相邻的两个元素

题目：给定一个链表，交换每个相邻的元素，最后返回新的链表节点。

ListNode *swapNodes(ListNode *head)
{if(head == NULL || head->next == NULL)return head;ListNode *dummyNode = new ListNode(0);dummyNode->next = head;ListNode *tmpNode = dummyNode;while(tmpNode->next != NULL && tmpNode->next->next != NULL){//用于临时存储一个节点ListNode *prev = tmpNode->next;//改变两个节点prev节点的next指针tmpNode->next = tmpNode->next->next;prev->next = tmpNode->next->next;//改变两个节点的next指针tmpNode->next->next = prev;tmpNode = prev;}return dummyNode->next;
}

另一种写法:

原理一样,上一种方法只保留了要交换两元素的前一个元素(while循环内再借助临时变量完成指针转换),本方法保留了三个元素(两个要交换的元素及前一个元素),开头的两个元素交换的话前一个元素用dummyNode。

//另一种写法,原理一样,上一种方法只保留了要交换两元素的前一个元素(while循环内再借助用临时变量完成指针转换),本方法保留了三个(两个要交换的元素及前一个元素),开头的两个元素交换的话前一个元素用dummyNode。
ListNode *swapPairs(ListNode *head)
{if(head == NULL || head->next == NULL)return head;ListNode *dummyNode = new ListNode(0);dummyNode->next = head;ListNode *prev = dummyNode;ListNode *node1 = head, node2 = head->next;while(node1 != NULL && node1->next != NULL){//三个元素都有了,prev、node1、node2node2 = node1->next;//改变两个元素prev节点的next指针prev->next = node2;node1->next = node2->next;//改变两个元素的next指针node2->next = node1;prev = node1;node1 = prev->next;}return dummyNode->next;        
}