数据结构基础知识04--高考信息技术一轮，二轮复习 数据结构基础知识（浙教版2019）

数据结构基础知识（四） 【知识要点】 给定一个单链表及其头节点head，请你反转链表，并返回反转后的链表。 def pList(n): while n != -1: if L[n][1] != -1: # 如果下一个还有数据，后面跟上">" print(L[n][0], end=">") else: print(L[n][0]) n = L[n][1] L = [["A", 3], ["C", 4], ["D", -1], ["E", 6],["B", 7], ["G", 0], ["F", 2], ["N", 5]] # 初始链表 head = 1 # 链表头指针指向1 print(L) pList(head) 输出结果： 列表显示为：[["A", 3], ["C", 4], ["D", -1], ["E", 6],["B", 7], ["G", 0], ["F", 2], ["N", 5]] 链表节点显示为：C>B>N>G>A>E>F>D 第一种方法：使用头插法完成单向链表的反转 解题思路： 1.创建一个空链表res，然后开始遍历原链表 2.对于遍历到的每一个结点，都将其作为res的头结点,那么当遍历到最后，也就完成了反转的目的 3.细节处是我们每一次循环，都要存储当前遍历结点的next结点，方便我们下次遍历，不然会死循环 k=head;newhead=-1 while head != -1: head=L[head][1] L[k][1]=newhead newhead=k k=head print(L) pList(newhead) 输出结果： 列表显示为：[["A", 5], ["C", -1], ["D", 6], ["E", 0],["B", 1], ["G", 7], ["F", 3], ["N", 4]] 链表节点显示为：D>F>E>A>G>N>B>C 第二种方法：双指针实现链表反转 prev = head #初始化存储前驱指针的变量 cur = L[head][1] #初始化存储当前节点的变量 L[head].append(L[head][1]) #先加入头指针的后继 L[head][1] = -1 #头节点单独操作,其前驱指针为-1 while len(L[cur]) == 2: #为其余节点添加前驱指针 L[cur].append(L[cur][1]) # 加入当前指针的后继 next = L[cur][1] #存储后继指针 L[cur][1]=prev #修改当前节点的前驱指针prev prev=cur #记录下一个节点的前驱指针prev cur=next #记录当前节点的后继指针cur tail=head # 初始化尾节点的位置 while L[tail][2] != -1: # 找反向的头指针位置 tail=L[tail][2] print(L) # 打印链表列表 pList(tail) # 调用函数输出链表 列表显示为：[['A',5,3],['C',-1,4],['D',6,-1],['E',0,6],['B',1,7],['G',7,0],['F',3,2],['N',4,5]] 链表节点显示为：D>F>E>A>G>N>B>C 第三种方法：栈实现链表反转 这种方法的思路是最简单的，因为栈本身就是实现线性结构倒序的常用工具。因为是牺牲空间换取时间的做法，执行时间应该会比较短，但有较大空间消耗。这里申请一个存放节点的栈，将所有节点入栈，再按出栈顺序重构链表，最终的结果就是反转的结果。仍要注意在反转过后要将原head节点的next指针置空。 s = [];top=-