246
題目：將鏈表的奇數位和偶數位調換組成新的鏈表
題目：將鏈表的奇數位和偶數位調換組成新的鏈表
原題鏈接: https://oj.leetcode.com/problems/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
# 分析
struct ListNode* swapPairs(struct ListNode* head)
Q1
Given 1->2->3->4, you should return the list as 2->1->4->3
head指向第一個元素 1 函數指針傳遞是傳遞 無論如何交換參數head
不可能返回指向元素2 如何解決？
- 必須重新建立一個新的鏈表 進行返回
-
采用 帶頭節點單鏈表
知識補充：帶頭節點單鏈表和不帶頭節點單鏈表有什麼區別
****
帶頭結點單鏈表好處解決了 不用判斷第一個節點是否為空 不需要特殊處理
用統一方法實現就 例如 鏈表insert操作******
**
返回值是最新鏈表 struct ListNode* head 不是**
Q2： 鏈表遍曆操作 ptr(A)=ptr->next(B) 前提條件節點A和節點B 位置關係沒有發現變化
在鏈表排序（交換位置是排序一個方法）原來位置發生改變如何處理 ？
需要臨時遍曆記錄 下 B位置
-
鏈表交換節點 影響不是2個 而是三個 不要忘記最後
1 -2-3 A=2 B=3
2-1-3 A=2 B=1 >>A=1 B=3解題思路如下
第一次循環處理結果：
root： 0 ->1->2->3 ->4 之前 pre=0 cur=1
root： 0 ->2->1->3->4 之後 pre=1 cur=3
pre相對於原來排序移動2次
code
/**
* 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)
{
//head節點
ListNode root(0);
root.next =head;
ListNode * pre=&root;//0
ListNode * cur =head;//1
while(cur && cur->next)
{
//swap
pre->next=cur->next;// 0 --> 2
cur->next=pre->next->next;//1 --> 3
pre->next->next=cur;//2->1
pre=cur;// 雖然 pre 仍然指向 位置1 原來位置1 swap之後放到位置2後麵
cur=cur->next;//pre ->1 cur->3 節
//0 ->2->1->3->4
}
return root.next;
}
};
執行行效率分析：
https://leetcode.com/submissions/detail/102239317/
耗時6ms不是最優解呀
耗時應該在建立頭節點
如果不用頭節點 需要特殊處理 第一次處理時候null
查看耗時3秒的 提取到函數外麵 為了防止異常數據 異常判斷
**為了完成遍曆 采用三個節點 first second three 三個節點 **
最後更新：2017-05-08 01:30:57