劍指offer 鏈表(上)
目錄
T6-從尾到頭打印鏈表
用棧保存ListNode指針 CPP
或者用stack保存順序節點的val也可以。 做此題時，第一個直觀的想法是順序讀鏈表時每次在res列表頭部插入元素，可以ac然而verctor最可怕的在頭部插入，可能需要多次重新分配空間，復制很多次元素
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> res;
stack<ListNode*> s;
ListNode *p=head;
while(p){
s.push(p);
p=p->next;
}
while(!s.empty()){
p=s.top();
res.push_back(p->val);
s.pop();
}
return res;
}
};
用棧保存val py2
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回從尾部到頭部的列表值序列，例如[1,2,3]
def printListFromTailToHead(self, listNode):
# write code here
value = []
while listNode:
value.append(listNode.val)
listNode=listNode.next
n=len(value)
res=[]
for i in range(n):
res.append(value.pop()) #Python的pop()函數有返回值奧
return res
參考
cpp中stack的函數
#include <stack>
using std::stack;
stack <類型> 變量名;
##### 接下來是一些關于棧的基本操作~
stack <int> s;（以這個為例子）
1.把元素a加入入棧：s.push(a);
2.刪除棧頂的元素：s.pop(); //返回void
3.返回棧頂的元素：s.top();
4.判斷棧是否為空：s.empty();（為空返回TRUE）
5.返回棧中元素個數：s.size();
6.把一個棧清空：（很抱歉沒有這個函數，你得寫這些：）
while (!s.empty())
s.pop();
cpp中vertor的函數
#include <vector>
using std::vector;
>初始化方式
vector<T> v1; //默認構造，v1 為空
vector<T> v2(v1); //v2 是 v1 的副本
vector<T> v3(n, i); //v3 包含 n 個 i 的元素
vector<T> v4(n); //v4 初始化為含有 n 個 T 類型默認值的對象
vector<int> v5 = {1,2,3,4,5,6,7}; //C++11才支持，直接值初始化，最方便
>插入元素
v5.insert(v2.begin()+4, 3); //在指定位置，例如在第五個元素前插入一個元素
v2.insert(v2.end(), 3); //在末尾插入一個元素
v2.push_back(9); //在末尾插入一個元素
v2.insert(v2.begin(), 3); //在開頭插入一個元素
>刪除元素
v2.erase(v2.begin()); //刪除開頭的元素
v2.erase(v2.begin(),v2.end); //刪除[begin,end]區間的元素
v2.pop_back(); //刪除最后一個元素
>其他
v.empty(); //v 為空，返回true
v.size(); //返回 v 中的個數
v.clear(); //移除容器中所有數據
py中棧是由list實現的， collections模塊里有deque雙向隊列
list.pop()返回值是拋出的元素
py中list的函數
list.append(x) #把一個元素添加到列表的結尾，相當于 a[len(a):] = [x]。
list.extend(L) #通過添加指定列表的所有元素來擴充列表，相當于 a[len(a):] = L。
list.insert(i, x) #在指定位置插入一個元素。第一個參數是準備插入到其前面的那個元素的索引，例如 a.insert(0, x) 會插入到整個列表之前，而 a.insert(len(a), x) #相當于 a.append(x) 。
list.remove(x) #刪除列表中值為 x 的第一個元素。如果沒有這樣的元素，就會返回一個錯誤。
list.pop([i]) #從列表的指定位置移除元素，并將其返回。如果沒有指定索引，a.pop()返回最后一個元素。元素隨即從列表中被移除。（方法中 i 兩邊的方括號表示這個參數是可選的，而不是要求你輸入一對方括號，你會經常在 Python 庫參考手冊中遇到這樣的標記。）
list.clear() #移除列表中的所有項，等于del a[:]。
list.index(x) #返回列表中第一個值為 x 的元素的索引。如果沒有匹配的元素就會返回一個錯誤。
list.count(x) #返回 x 在列表中出現的次數。
list.sort() #對列表中的元素進行排序。
list.reverse() #倒排列表中的元素。
list.copy() #返回列表的淺復制，等于a[:]。
T25-合并兩個排序的鏈表
我下意識的非遞歸版本 py2
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回合并后列表
def Merge(self, pHead1, pHead2):
# write code here
if pHead1 is None and pHead2 is None:
return pHead1
p1 = pHead1
p2 = pHead2
p = ListNode(0)
pres = p
while p1 or p2:
if p1 and p2:
if p1.val<=p2.val:
p.next = p1
p1 = p1.next
else:
p.next = p2
p2 = p2.next
elif p1:
p.next = p1
break
else:
p.next = p2
break
p = p.next
return pres.next
遞歸版本 py2
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回合并后列表
def Merge(self, pHead1, pHead2):
# write code here
if pHead1 is None:
return pHead2
if pHead2 is None:
return pHead1
pHead = ListNode(0)
if pHead1.val<=pHead2.val:
pHead = pHead1
pHead.next = self.Merge(pHead1.next,pHead2)
else:
pHead = pHead2
pHead.next = self.Merge(pHead1,pHead2.next)
return pHead
稍有不同的寫法
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回合并后列表
def Merge(self, pHead1, pHead2):
# write code here
if pHead1 is None:
return pHead2
if pHead2 is None:
return pHead1
if pHead1.val<=pHead2.val:
pHead1.next = self.Merge(pHead1.next,pHead2)
return pHead1
else:
pHead2.next = self.Merge(pHead1,pHead2.next)
return pHead2
T52-兩個鏈表的第一個公共節點
兩路鏈表走同樣的長度 py
>兩個鏈表走到各自的尾端然后跳到另一條鏈表的開頭，相遇時走了同樣的(a+b+c)長度，同樣的思路，我寫的就串行用了好多個while循環，慘不忍睹，人家用了選擇表達式就非常簡潔
```
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def FindFirstCommonNode(self, pHead1, pHead2):
# write code here
if pHead1 is None or pHead2 is None:
return None
p1, p2 = pHead1, pHead2
while p1!=p2:
p1 = pHead2 if p1 is None else p1.next
p2 = pHead1 if p2 is None else p2.next
return p1
```
## 官方推薦 記錄鏈表的長度 暫未實現
>分別走完兩個鏈表，記錄長度，然后長鏈表上一個指針從等于鏈表差值的位置出發，短鏈表從頭出發，二者相遇位置為第一個共同節點
棧保存節點，然后從尾開始pop，比較 不推薦 py2
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def FindFirstCommonNode(self, pHead1, pHead2):
# write code here
if not pHead1 or not pHead2:
return None
p1, p2 = pHead1, pHead2
stack1,stack2 = [],[]
while p1:
stack1.append(p1)
p1 = p1.next
while p2:
stack2.append(p2)
p2 = p2.next
first = None
while stack1 and stack2:
p1 = stack1.pop()
p2 = stack2.pop()
if p1==p2:
first = p1
else:
break
return first
T23-鏈表中環的入口節點
快慢指針 py2
設置快慢指針，都從鏈表頭出發，快指針每次走兩步，慢指針一次走一步，假如有環，一定相遇于環中某點(結論1)。接著讓兩個指針分別從相遇點和鏈表頭出發，兩者都改為每次走一步，最終相遇于環入口(結論2)。以下是兩個結論證明：
兩個結論：
1、設置快慢指針，假如有環，他們最后一定相遇。
2、兩個指針分別從鏈表頭和相遇點繼續出發，每次走一步，最后一定相遇與環入口。
證明結論1：設置快慢指針fast和low，fast每次走兩步，low每次走一步。假如有環，兩者一定會相遇（因為low一旦進環，可看作fast在后面追趕low的過程，每次兩者都接近一步，最后一定能追上）。
證明結論2：
設：
鏈表頭到環入口長度為--a
環入口到相遇點長度為--b
相遇點到環入口長度為--c
則：相遇時
快指針路程=a+(b+c)k+b ，k>=1 其中b+c為環的長度，k為繞環的圈數（k>=1,即最少一圈，不能是0圈，不然和慢指針走的一樣長，矛盾）。
慢指針路程=a+b
快指針走的路程是慢指針的兩倍，所以：
（a+b）*2=a+(b+c)k+b
化簡可得：
a=(k-1)(b+c)+c 這個式子的意思是： 鏈表頭到環入口的距離=相遇點到環入口的距離+（k-1）圈環長度。其中k>=1,所以k-1>=0圈。所以兩個指針分別從鏈表頭和相遇點出發，最后一定相遇于環入口。
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def EntryNodeOfLoop(self, pHead):
# write code here
fast,slow = pHead,pHead
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if fast==slow:
break
if not fast or not fast.next:
return None
fast = pHead
while fast!=slow:
slow = slow.next
fast = fast.next
return fast
用set()存放節點 一般吧 py2
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def EntryNodeOfLoop(self, pHead):
# write code here
if not pHead:
return None
p1=pHead
d = set()
while p1:
if p1 in d:
return p1
else:
d.add(p1)
p1 = p1.next
浙公網安備 33010602011771號