[数据结构与算法]学IT，找工作——反转链表

206. 反转链表

给定单链表的头节点 head ，反转链表，并返回反转后的链表。

解：

在脑海里模拟一个形象的解法：

• 我们现在有两个糖葫芦串，分别是旧的串子和新的串子，打算把山楂球从旧串子串到新串子上。

• 做法就是：

  1. 从旧串子上把最顶上的那颗山楂球摘下来，然后插到新的串子上
  2. 摘下来的山楂球就将是新串的头部。
  3. 顺便维护一下新串中山楂球的前后关系。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # 新串子
        head2 = None
        # 从旧串子上把山楂球挨个撸下来
        traverse = head
        # 辅助撸旧串子的变量
        pointer = None
        
        while traverse != None:
            # 从旧串上把最顶上的那颗山楂球摘下来，然后插到新的串上
            pointer = traverse.next
            # 从旧串上新摘下来的山楂球就将是新串的头部。
            traverse.next = head2
            head2 = traverse
            # 顺便维护一下新串中山楂球的前后关系。
            traverse = pointer

        return head2