刷题篇--反转链表I、II

反转链表

反转链表是面试题目中的经典题目，是必须要掌握的，其有各种变形，如只反转某部分、按K个一组反转等。本文主要实现leetcode中的反转链表I、II。

1.反转链表I

leetcode 206，反转链表涉及链表知识，需要指针操作，需要注意的就是指针如何动的问题。

def reverseList(head): if head is None or head.next is None: return head #特判 cur = head #定义三个指针，进行后续反转 pre = None next_node = None while cur: #当cur为None时说明每个节点都遍历完了 next_node = cur.next cur.next = pre pre = cur cur = next_node return pre #此时pre指向的才是反转后的头指针

该过程大家手推一遍就可以清楚整个流程。

2.反转链表II

leetcode 92，该题与反转链表I的不同在于其需要反转指定节点。该题需要注意的是我们对于头节点如何处理，最好是能够与其他节点操作一样，所以需要引入头节点。

def reverseBetween(head, m, n): if head is None or head.next is None: return head headnode = ListNode(None) #生成头节点 headnode.next = head tmp = headnode for i in range(m-1): #定位到要反转的第一个节点的前一个节点，为了保证不断链 tmp= tmp.next cur = tmp.next #定义指针进行反转 pre = None next_node = None for i in range(n-m+1): #m-n进行反转，为n-m+1的原因大家了解反转链表的过程就能够容易得出 next_node = cur.next cur.next = pre pre = cur cur = next_node tmp.next.next = cur #将断掉的链连起来，使用tmp.next.next是因为tmp.next一直指向着要反转的第一个节点 tmp.next = pre return headnode.next