链表

实现单链表、循环链表、双向链表，支持增删操作
实现单链表反转
实现两个有序的链表合并为一个有序链表
实现求链表的中间结点

实现单链表、循环链表、双向链表，支持增删

循环链表的操作和单链表基本一致，差别仅在于算法中的循环条件不是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;
}

}

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;
    }
};

与链表中环的检测一样，这题同样可以使用快慢指针来解决。

定义两个指针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