一、题目：判断一个链表是否为回文结构
简单思路：时间O（N)，空间O（N）
采用栈来存储链表值，再从栈中弹出值（逆序），如果和链表顺序值一样，则为回文结构。
eg：1→2→1，顺序：121，倒序：121。则为回文。
1→3→2，顺序：132，倒序：231，不为回文。
代码：
class Node: def __init__(self,value): self.value = value self.next = None def isPal(head): stack = [] if not head: return False while head: stack.append(head.value) head = head.next if stack == stack[::-1]: return True else: return False head = Node(1) head.next = Node(2) head.next.next = Node(3) isPal(head)
空间省一半的思路：时间O（N)，空间O（N/2）
栈中只存链表后一半的值。再与链表前一半对比。
代码：
class Node: def __init__(self,value): self.value = value self.next = None def isPal(head): if not head: return head stack = [] cur , right = head , head
#找到中间节点 while cur.next and cur.next.next: right = right.next cur = cur.next.next
#将链表右边部分存进栈中 while right: stack.append(right) right = right.next
#将栈和链表左半部分对比 while stack: if head.value != stack[-1]: return False del stack[-1] head = head.next return True head = Node(1) head.next = Node(2) head.next.next = Node(3) isPal(head)
进阶思路：时间O（N)，空间O（1）
将链表后半部分反转，再与前半部分对比，就不需要新的栈来存储。
代码：
class Node: def __init__(self,value): self.value = value self.next = None def isPal(head): if not head: return head cur , right = head , head
#找到中间节点 while cur.next and cur.next.next: right = right.next cur = cur.next.next mid = right first = right
#将链表后半部分反转 while right.next: temp = right.next right.next = right.next.next temp.next = first first = temp
#将链表前半部分和后半部分对比 while head: if first.value != head.value: return False first = first.next head = head.next return True head = Node(1) head.next = Node(2) head.next.next = Node(3) head.next.next.next = Node(3) head.next.next.next.next = Node(2) head.next.next.next.next.next = Node(1) isPal(head)
二、题目：单链表生成相加链表
简单思路：时间O（N），空间O（N）
直接将链表中的数值读取出来转化成整型数据，再相加，之后再将值存储到链表中。但是这种做法有个问题，当链表长度太长，转成int时容易溢出。
进阶思路1：时间O（N），空间O（N），用栈
利用栈结构来存储链表中的数值，然后再每一位进行相加计算。
代码：
import queue class Node: def __init__(self,value): self.value = value self.next = None def mullist(head1,head2): if not head1 and not head2: return 0 cur1 = head1 cur2 = head2 stack1 = queue.LifoQueue() stack2 = queue.LifoQueue() while cur1: stack1.put(cur1.value) cur1 = cur1.next while cur2: stack2.put(cur2.value) cur2 = cur2.next ca = 0 #进位符 node , pre = Node(None) , Node(None) while not stack1.empty() or not stack2.empty(): n1 = stack1.get() if not stack1.empty() else 0 n2 = stack2.get() if not stack2.empty() else 0 mul = ca + n1 + n2 ca = mul // 10 pre = node node = Node(mul%10) node.next = pre if ca == 1: node = Node(1) pre = node node.next = pre return node if __name__ == '__main__': head1 = Node(1) p = head1 for i in range(2,3): p.next = Node(i) p = p.next head2 = Node(6) p1 = head2 for i in range(7,8): p1.next = Node(i) p1 = p1.next res = mullist(head1,head2)