Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
..
Failed to load latest commit information.
02.AddTwoNumbers.py
138_CopyListWithRandomPointer.py
143_ReorderList.py
147_InsertionSortList.py
148_SortList.cpp
148_SortList.py
160_IntersectionOfTwoLinkedLists.cpp
160_IntersectionOfTwoLinkedLists.py
203_RemoveLinkedListElements.py
206_ReverseLinkedList.cpp
206_ReverseLinkedList.py
21_MergeTwoSortedLists.cpp
21_MergeTwoSortedLists.py
234_PalindromeLinkedList.py
237_DeleteNodeInLinkedList.py
24_SwapNodesInPairs.py
25_ReverseNodesIn-k-Group.py
328_OddEvenLinkedList.py
61_RotateList.cpp
61_RotateList.py
76_MinimumWindowSubstring.py
82_RemoveDuplicatesFromSortedListII.cpp
82_RemoveDuplicatesFromSortedListII.py
83_RemoveDuplicatesFromSortedList.cpp
83_RemoveDuplicatesFromSortedList.py
86_PartitionList.py
92_ReverseLinkedListII.py
README.md

README.md

链表概述

我们知道用数组存放数据时,必须事先定义数组的长度(即元素个数)。当事先难以确定有多少个元素时,则必须把数组定义的足够大,以保证成功。无疑,这会造成内存浪费。因此可以考虑设计一种物理存储单元上非连续、非顺序的存储结构,来避免数组带来的问题,链表正是这样的一种数据结构。

链表由一系列结点(链表中每一个元素称为结点)组成,每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。

结点可以在运行时动态生成。

数据元素的逻辑顺序则是通过链表中的指针链接次序实现的。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。

链表特点

头指针 指链表中第一个结点(即第一个数据元素)的存储位置。

有时为了简化链表的操作,在链表的第一个结点之前附设一个结点,称之为头结点。头结点的数据域可以不存储任何信息,也可以存储如线性表长度等类的附加信息,头结点的指针域存储指向第一个结点的指针(即第一个元素结点的存储位置)。

最后一个数据元素没有直接后继,所以线性链表中最后一个结点的指针域为“空”(NULL)。

链表操作

单链表排序

题目

206 Reverse Linked List

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

可以用递归或者迭代实现,关键在于要注意结点为 NULL 的情况。

具体代码

更多阅读

Wikipedia: Linked_list