# -*- coding:utf8 -*- #/usr/bin/env python class Node(object): def __init__(self, data, pnext = None): self.data = data self._next = pnext print('self._next',self._next) def __repr__(self): return str(self.data) class ChainTable(object): def __init__(self): self.head = None self.length = 0 def isEmpty(self): return (self.length == 0) def append(self, dataOrNode): item = None print('Node',Node) if isinstance(dataOrNode, Node): item = dataOrNode print(123) else: item = Node(dataOrNode) print(item,456) if not self.head: self.head = item self.length += 1 print('self.head',self.head._next) else: node = self.head print('1111node',node) print('111node._next',node._next) while node._next: print(222222222222222222222222,node._next) node = node._next print(444444444444444,node) node._next = item print(11111111111111111111111,node._next) self.length += 1 def reverseChainTable(self,chaintable): if isinstance(chaintable, Node): item = chaintable print(123) else: print('这不是链表') return def delete(self, index): if self.isEmpty(): print ("this chain table is empty.") return if index < 0 or index >= self.length: print ('error: out of index') return if index == 0: self.head = self.head._next self.length -= 1 return j = 0 node = self.head prev = self.head while node._next and j < index: prev = node node = node._next j += 1 if j == index: prev._next = node._next self.length -= 1 def insert(self, index, dataOrNode): if self.isEmpty(): print ("this chain tabale is empty") return if index < 0 or index >= self.length: print ("error: out of index") return item = None if isinstance(dataOrNode, Node): item = dataOrNode else: item = Node(dataOrNode) if index == 0: item._next = self.head self.head = item self.length += 1 return j = 0 node = self.head prev = self.head while node._next and j < index: prev = node node = node._next j += 1 if j == index: item._next = node prev._next = item self.length += 1 def update(self, index, data): if self.isEmpty() or index < 0 or index >= self.length: print ('error: out of index') return j = 0 node = self.head while node._next and j < index: node = node._next j += 1 if j == index: node.data = data def getItem(self, index): if self.isEmpty() or index < 0 or index >= self.length: print ("error: out of index") return j = 0 node = self.head while node._next and j < index: node = node._next j += 1 return node.data def getIndex(self, data): j = 0 if self.isEmpty(): print ("this chain table is empty") return node = self.head while node: if node.data == data: return j node = node._next j += 1 if j == self.length: print ("%s not found" % str(data)) return def clear(self): self.head = None self.length = 0 def __repr__(self): if self.isEmpty(): return "empty chain table" node = self.head nlist = '' while node: nlist += str(node.data) + ' ' node = node._next return nlist def __getitem__(self, ind): if self.isEmpty() or ind < 0 or ind >= self.length: print ("error: out of index") return return self.getItem(ind) def __setitem__(self, ind, val): if self.isEmpty() or ind < 0 or ind >= self.length: print ("error: out of index") return self.update(ind, val) def __len__(self): return self.length chariin = ChainTable() for i in range(10): chariin.append(i) print(chariin)
从哪里找的忘了，不过思路已经整的很明白了
下面是链表翻转的：
来源 https://blog.csdn.net/u011608357/article/details/36933337
单链表的反转可以使用循环，也可以使用递归的方式
1.循环反转单链表
循环的方法中，使用pre指向前一个结点，cur指向当前结点，每次把cur->next指向pre即可。
class ListNode: def __init__(self,x): self.val=x; self.next=None; def nonrecurse(head): #循环的方法反转链表 if head is None or head.next is None: return head; pre=None; cur=head; h=head; while cur: h=cur; tmp=cur.next; cur.next=pre; pre=cur; cur=tmp; return h; head=ListNode(1); #测试代码 p1=ListNode(2); #建立链表1->2->3->4->None; p2=ListNode(3); p3=ListNode(4); head.next=p1; p1.next=p2; p2.next=p3; p=nonrecurse(head); #输出链表 4->3->2->1->None while p: print p.val; p=p.next;
反转代码：
class ListNode: def __init__(self,x): self.val=x; self.next=None; def recurse(head,newhead): #递归，head为原链表的头结点，newhead为反转后链表的头结点 if head is None: return ; if head.next is None: newhead=head; else : newhead=recurse(head.next,newhead); head.next.next=head; head.next=None; return newhead; head=ListNode(1); #测试代码 p1=ListNode(2); # 建立链表1->2->3->4->None p2=ListNode(3); p3=ListNode(4); head.next=p1; p1.next=p2; p2.next=p3; newhead=None; p=recurse(head,newhead); #输出链表4->3->2->1->None while p: print p.val; p=p.next;