剑指Offer[24]-反转链表

题目

定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

python代码

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # step 1
        if not head:
            return None
        if not head.next:
            return head
        # step 2
        pre_head = head.next
        cur_head = head
        out_head = None
        # step 3
        while pre_head:
            cur_head.next = out_head
            out_head = cur_head
            cur_head = pre_head
            pre_head = pre_head.next
        cur_head.next = out_head
        return cur_head

这道题也是链表类题目中具有代表性的题目,重点考察了链表中如何连续改变节点间的连接关系时。

  • step 1.首先考虑特殊情况,当输入为None或者只有一个节点时,就直接返回。
  • step 2. 例如有链表A->B->C->D,我们要将节点B和C反过来,也就是新的链表为A->C->B->D。首先,我们要断开A->B、B->C及C->D的连接,然后重新连接A->C、C->B及B->D,而在本题中,我们要遍历一遍链表,像这样的断开连接并重新连接需要很多次,所以我们需要使用三个额外的节点,在断开连接时,来保持这三个连接关系(其实大家可以简单把这种连接关系画出来,然后模拟断开连接并重新连接,就会明白为什么需要三个额外的节点)
  • step 3. 遍历整个链表,每次反转两个节点的连接关系,并更新三个外节点的指向,以便下次循环

这是链表里面比较常规的题目,需要明确链表的特点,适当构造额外辅助的节点,更直观地可以画出各节点之间的关系图,这样解题思路也就很清晰了。

发表评论

电子邮件地址不会被公开。