python实现反转部分单向链表

时间:2022-12-09 08:41:33

题目:

给定一个单链表的头指针 head, 以及两个整数 a 和 b,在单链表中反转 linked_list[a-b] 的结点,然后返回整个链表的头指针。
例如:
单链表[1000, 5, 12, 100, 45, ‘cecil', 999],
a = 4, b = 6,
返回的链表是[1000, 5, 12, 100, 999, ‘cecil', 45],也就是说,
a 和 b分别为索引值。如果a 和 b 超过了索引范围就返回错误。

代码:

我写的不够简洁,比较繁琐,但是能跑通,繁琐的原因在于我使用了 for 循环,对于 a == 0 的情况 for 循环无法识别。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def reverse_part_linked_list(head, a, b): # 反转部分链表结点,a, b分别为索引值
  if head == 0:
    print "Empty linked list. No need to reverse."
    return head
  p = head
  length = 1
  while p != 0:
    length += 1
    p = p.next
  if length == 1:
    print "No need to reverse."
    return head
  if a < 0 or b > length-1 or a >= b:
    raise Exception("The given 'from' value and 'to' value is wrong.")
  p = head
 
  if a == 0: # 由于 for 循环中 xrange 的范围问题,我就分情况写了。
    tail, head = p, p
    pre = 0
    for _ in xrange(a, b+1):
      p = p.next
      head.next = pre
      pre = head
      head = p
    tail.next = p
    return head
  else:
    for _ in xrange(1, a):
      p = p.next
    front, tail, head = p, p, p
    p = p.next
    pre = 0
    for _ in xrange(a+1, b+2):
      p = p.next
      head.next = pre
      pre = head
      head = p
    front.next = pre
    tail.next = p
    return head

分析:

核心依然是反转链表的指针问题,均是一遍循环,时间复杂度o(n),空间复杂度为若干个变量。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。

原文链接:https://blog.csdn.net/dongrixinyu/article/details/78660587