中文題目
給定一個鏈表，兩兩交換其中相鄰的節(jié)點露该，并返回交換后的鏈表睬棚。
示例:
給定 1->2->3->4, 你應(yīng)該返回 2->1->4->3.
說明:
- 你的算法只能使用常數(shù)的額外空間。
- 你不能只是單純的改變節(jié)點內(nèi)部的值解幼，而是需要實際的進行節(jié)點交換抑党。
英文題目
Given a linked list, swap every two adjacent nodes and return its head.
Example:
Given 1->2->3->4, you should return the list as 2->1->4->3.
Note:
- Your algorithm should use only constant extra space.
- You may not modify the values in the list's nodes, only nodes itself may be changed.
剛看到本題之時，我開始動手做撵摆，腦殘的我剛開始寫了一個極為簡練的代碼底靠，卻發(fā)現(xiàn)自己只是在交換自己新建的結(jié)點，原鏈表并無變化特铝，這里就不貼出了暑中。壹瘟。。
經(jīng)查找鳄逾，發(fā)現(xiàn)以下解法
解法：
本題可以說是一個非车竟欤基本的題，考的是鏈表的結(jié)點交換雕凹，重點在于不丟失鏈表地址
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* swapPairs(struct ListNode* head) { // LeetCode24
if (head == NULL || head->next == NULL) // 僅有0或1個結(jié)點 直接返回
return head;
struct ListNode* newHead, *p, *q, *temp;
/* 下面的開空間必不可少 否則會報錯 */
newHead = (struct ListNode*)malloc(sizeof(struct ListNode));
newHead->next = head;
/* 初始化 */
temp = newHead;
p = head;
q = head->next;
while (q){
/*交換操作*/
temp->next = q;
p->next = q->next; /* 整個交換的重點 將q之后的結(jié)點掛在p之后 */
q->next = p;
/*為下次操作準(zhǔn)備*/
temp = p;
p = p->next;
if (p)
q = p->next;
else
q = NULL;
}
return newHead->next;
}
代碼說明：
- 首先殴俱，為鏈表設(shè)置一個頭結(jié)點，防止鏈表丟失
- 初始化p枚抵，q线欲，temp結(jié)點
- 開始交換，直至q結(jié)點為空
- 返回交換后的鏈表
提交結(jié)果：
leetcode24.png
