- 实现单链表、循环链表、双向链表，支持增删操作
- 实现单链表反转
- 实现两个有序的链表合并为一个有序链表
- 实现求链表的中间结点
实现单链表、循环链表、双向链表，支持增删
循环链表的操作和单链表基本一致，差别仅在于算法中的循环条件不是L或L->为空，而是它们是否等于头指针，因为当循环到头指针，说明链表已经完整遍历一次，下面给出代码：
实现单链表反转
#include<iostream>
#include<cstdlib>
using namespace std;
class list{
public:
int data;
class list *next;
};
typedef class list node;
typedef node *link;
link FindNode(link head,int position_data){
link phead;
phead = head;
while(phead != NULL){
if(phead->data == position_data)return phead;
phead = phead->next;
}
return phead;
}
link InsertNode(link head,int position_data,int data){
link phead = new node;
phead = FindNode(head,position_data);
link insertnode = new node;
if(!insertnode) return NULL;
insertnode->data = data;
insertnode->next = NULL;
if(phead == NULL){ //插入第一个节点
insertnode->next = head;
return insertnode;
}
else if(phead->next == NULL) phead->next = insertnode; //插入最后一个节点
else{ //插入中间节点
insertnode->next = phead->next;
phead->next = insertnode;
}
return head;
}
link DeleteNode(link head,int position_data){
link top = head; //保留头指针
link phead = FindNode(head,position_data);
if(head == phead){ //删除头结点
head = head->next;
delete phead;
}
else{
while(top->next != phead) top = top->next;
if(phead->next == NULL){ //删除尾结点
top->next = NULL;
delete phead;
}
else{
top->next = phead->next;
delete phead;
}
}
return head;
}
link InvertList(link head){
link pre,phead,temp;
phead = head; //将phead指向链表头，做游标使用
pre = NULL; //pre为头指针之前的节点
while(phead != NULL){
temp = pre;
pre = phead;
phead = phead->next;
pre->next = temp; //pre接到之前的节点
}
return pre;
}
link CreateList(int a[],int n){
link head,phead,newnode;
phead = new node;
if(!phead) return NULL;
phead->data = a[0];
head = phead;
for(int i = 1;i<n;i++){
newnode = new node;
newnode->data = a[i];
newnode->next = NULL;
phead->next = newnode;
phead = phead->next;
}
return head;
}
void PrintList(link head){
link phead = new node;
phead = head;
cout<<"链表元素如下: "<<endl;
while(phead!=NULL){
cout<<phead->data<<"->";
head = phead;
phead = phead->next; //phead按序往后遍历整个链表
if(!phead) cout<<"NULL"<<endl;
}
}
int main(){
int position_data,data;
link head,phead;
int n;
cout<<"请输入初始链表元素个数: "<<endl;
cin>>n;
int a[n];
cout<<"请依次输入链表元素: ";
for(int i = 0;i<n;i++) cin>>a[i];
head = CreateList(a,n);
PrintList(head);
cout<<"请输入预插入位置之前的元素和要插入的元素（例：5 8）: ";
cin>>position_data>>data;
head = InsertNode(head,position_data,data);
cout<<"插入之后的";
PrintList(head);
cout<<"请输入想删除的链表元素: ";
cin>>position_data;
head = DeleteNode(head,position_data);
cout<<"删除之后的";
PrintList(head);
cout<<"反转之后的";
head = InvertList(head);
PrintList(head);
return 0;
}
————————————————
版权声明：本文为CSDN博主「学习要有深度」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_36472818/article/details/96379507
实现两个有序的链表合并为一个有序链表
- // 链表类：
- struct ListNode{
- int val;
- ListNode *next;
- ListNode (int x): val(x), next(NULL) {}
- };
// 合并两个有序链表：
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
{
if (l1 == NULL)
return l2;
if (l2 == NULL)
return l1;
ListNode *pre = new ListNode(0);
ListNode *head = pre;
while (l1 != NULL && l2 !=NULL)
{
if(l1->val > l2->val)
{
head->next = l2;
l2 = l2->next;
}
else
{
head->next = l1;
l1 = l1->next;
}
head = head->next;
}
if (l1 == NULL)
{
head->next = l2;
}
if (l2 == NULL)
{
head->next = l1;
}
return pre->next;
}
ListNode* mergeTwoLists(ListNode* p1, ListNode* p2)
{
if(p1 == NULL)
return p2;
else if(p2 == NULL)
return p1;
ListNode* pMergedHead = NULL;
if(p1->val < p2->val)
{
pMergedHead = p1;
pMergedHead->next = mergeTwoLists(p1->next, p2);
}
else
{
pMergedHead = p2;
pMergedHead->next = mergeTwoLists(p1, p2->next);
}
return pMergedHead;
}
ListNode* mergeTwoLists(ListNode* p1, ListNode* p2)
{
if(p1 == NULL)
return p2;
else if(p2 == NULL)
return p1;
ListNode* pMergedHead = NULL;
if(p1->val < p2->val)
{
pMergedHead = p1;
pMergedHead->next = mergeTwoLists(p1->next, p2);
}
else
{
pMergedHead = p2;
pMergedHead->next = mergeTwoLists(p1, p2->next);
}
return pMergedHead;
}
int main()
{
ListNode n1(1), n2(3), n3(5), n4(7), n5(9);
n1.next = &n2;
n2.next = &n3;
n3.next = &n4;
n4.next = &n5;
ListNode m1(2), m2(4), m3(6), m4(8), m5(10);
m1.next = &m2;
m2.next = &m3;
m3.next = &m4;
m4.next = &m5;
ListNode *pMergedHead = new ListNode(0);
pMergedHead = mergeTwoLists(&n1, &m1)
while (pMergedHead != NULL)
{
cout << pMergedHead ->val << endl;
pMergedHead = pMergedHead ->next;
}
}
实现求链表的中间结点
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* middleNode(ListNode* head) {
if(head == nullptr) return head;
int cnt = 0;
ListNode* p = head->next;
while(p != nullptr)
{
cnt++;
p = p->next;
}
if(cnt % 2 == 0)
{
cnt = (cnt + 1) /2;
}
else
{
cnt = cnt / 2 + 1;
}
ListNode* q = head;
while(cnt != 0)
{
q = q->next;
cnt--;
}
return q;
}
};
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* middleNode(ListNode* head) {
if(head == nullptr) return head;
ListNode* p = head;
ListNode* q = head;
while(q != nullptr && q->next != nullptr)
{
p = p->next;
q = q->next->next;
}
return p;
}
};
与链表中环的检测一样，这题同样可以使用快慢指针来解决。
定义两个指针fast和slow。slow一次遍历一个节点，fast一次遍历两个节点，由于fast的速度是slow的两倍，所以当fast遍历完链表时，slow所处的节点就是链表的中间节点。
public static ListNode middleNode(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return fast == null ? slow : slow.next;
}
class Solution:
def hasCycle(self, head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow