014-链表中倒数第k个结点

用快慢指针：p2比p1先走k-1（1到k：间隔了k-1）步，然后再一起走，当p2为最后一个时，p1就为倒数第k个数

  1. class ListNode:
  2.     def __init__(self, x):
  3.         self.val = x
  4.         self.next = None
  6. class Solution:
  7.     def FindKthToTail(self, head, k):
  8.         if not head or k<=0: return None
  9.         p1 = head
  10.         p2 = head
  11.          #设置两个指针，p2指针先走（k-1）步，然后再一起走
  12.         while (k-1)>0:
  13.             if (p2.next != None):
  14.                 p2 = p2.next
  15.                 k -= 1
  16.             else:
  17.                 return None
  18.         while (p2.next != None): # 等同while p2.next:
  19.             p1 = p1.next
  20.             p2 = p2.next
  21.         return p1

 

 

015-反转链表（链表转化赋值）

思路：变化node.next

假设翻转1->2->3->4->5，（54321）

重要：

  • 1.构建辅助节点head
  • 2.我们将p的next指向tp的next
  • 3.将tp的next指向head的next
  • 4.将head的next指向tp 
  1. class ListNode:
  2.      def __init__(self, x):
  3.             self.val = x
  4.             self.next = None
  6. class Solution:
  7.     # 新链表的表头,不是head，是head.next
  8.     def ReverseList(self, pHead):
  9.         if not pHead:return None
  10.         #构建辅助节点head
  11.         head = ListNode(0)
  12.         head.next = pHead
  13.         p = pHead
  14.         while p.next != None:
  15.             #链表节点转化操作（重要）
  16.             tp = p.next
  17.             p.next = tp.next
  18.             tp.next = head.next
  19.             head.next = tp
  20.         return head.next

 

posted on 2019-06-20 22:19 5三金 阅读(…) 评论(…) 编辑 收藏

版权声明：本文为WuSehun原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/WuSehun/p/11061774.html