链表常用操作

阅读量：6978 次

发布时间：2019-06-27

本文共 5459 字，大约阅读时间需要 18 分钟。

转自：

数据结构之链表-链表实现及常用操作(C++篇)

0.摘要

定义

插入节点（单向链表）

删除节点（单向链表）

反向遍历链表

找出中间节点

找出倒数第k个节点

翻转链表

判断两个链表是否相交，并返回相交点

判断链表是否有环路，获取连接点，计算环的长度

二叉树和双向链表转化

1.定义

1.1单向链表

单向链表的节点包括：

数据域：用于存储数据元素的值。

指针域（链域）：用于存储下一个结点地址或者说指向其直接后继结点的指针。
```
struct Node{
       int value; Node * next; };
```

1.2双向链表

双向链表的节点包括：

数据域：用于存储数据元素的值。

左指针域（左链域）：用于存储上一个结点地址或者说指向其直接前继结点的指针。

右指针域（右链域）：用于存储下一个结点地址或者说指向其直接后继结点的指针。
```
struct DNode{
      int value; DNode * left; DNode * right; };
```

2.常用操作例题

2.1插入节点（单向链表）

//p节点后插入值为i的节点 void insertNode(Node p, int i){
    Node node = new Node; node->value = i; node->next = p->next; p->next = node; }

2.2删除节点（单向链表）

当需要删除一个节点p时，只需要将p的前一个节点的next赋为p->next,但是由于是单向的，只知道p，无法知道p前一个节点，所以需要转换思路。将p下一个的节点覆盖到p节点即可，这样就等效于将p删除了。

void deleteNode(Node p){
     p->value = p->next->value; p->next = p->next->next; }

2.3反向遍历链表

法一：反向遍历链表就类似于事先遍历的节点后输出，即“先进后出”，那么可以将链表遍历存放于栈中，其后遍历栈依次弹出栈节点，达到反向遍历效果。

//1.stack void printLinkedListReversinglyByStack(Node head){
    stack
     
       nodesStack; Node* pNode = head; //遍历链表 while (pNode != NULL) {
    nodesStack.push(pNode); pNode = pNode->next; } while (!nodesStack.empty()) {
    pNode=nodesStack.top(); printf("%d\t", pNode->value); nodesStack.pop(); } } //2.递归 void printLinkedListReversinglyRecursively(Node head){
    if (head!=NULL) {
    if (head->next!=NULL) {
    printLinkedListReversinglyRecursively(head->next); } printf("%d\t", head->value); } }

2.4找出中间节点

用slow和fast指针标记，slow每次走一步，fast每次走两步，当fast到尾节点时，slow就相当于总长度的一半，即在中间节点。

//找出中间节点 Node findMidNode(Node* head){
    Node* slow = head; Node* fast = head; while (fast->next != 0&&fast->next->next!=0) {
    slow = slow->next; fast = fast->next->next; } return slow; }

2.5找出倒数第k个节点

用slow和fast指针标记,fast指针事先走k步，然后slow和fast同时走，当fast到达末节点时，slow在fast的前k个节点，即为倒数第k个节点。

//找出倒数第k个节点 Node* findKNode(Node* head,int k){
    Node temp1 = head; Node temp2 = head; while (k-->0) {
    if(temp2 == NULL){
    return NULL; } temp2 =temp2->next; } while (temp2->next != NULL&&temp2->next->next!=NULL) {
    temp1 = temp1->next; temp2 = temp2->next->next; } return temp1; }

2.6翻转链表

题意即为将链表反过来，即，原本为p1-p2-p3翻转为p3-p2-p1。读者需自行画图体会指针操作。

//翻转链表 Node * reverseLinkedList(Node* head,int k){
    Node reversedHead = NULL; Node pNode = head; Node pre = NULL; while (pNode!=NULL) {
     if (pNode->next==NULL) {
     reversedHead = pNode; } Node nxt = pNode->next; pNode->next = pre; pre=pNode; pNode=nxt; } return reversedHead; }

2.7判断两个链表是否相交，并返回相交点

如果两个链表相交，其形状必为y形，而不可以能为x形，即两条链表必有相同的尾节点。首先，计算得到两个链表的长度:m,n，求得两个链表长度之差distance＝|m-n|，让较长得那个链表事先走distance步，这样，若是链表相交得话，二者指针必相撞，相撞点即为相交点。

Node* findCrosspoint(Node* l1, Node* l2){
    int m = getLinkedListLength(l1); int n = getLinkedListLength(l2); int distance=0; Node temp1= l1; Node temp2= l2; if (m>n) {
    distance = m - n; while (distance>0) {
    distance--; temp1=temp1->next; } } else{
    distance = n - m; while (distance>0) {
    distance--; temp2 = temp2->next; } } while(temp1!=temp2&&temp1->next!=NULL&&temp2->next!=NULL){
    temp1=temp1->next; temp2=temp2->next; } if(temp1 == temp2){
    return temp1; } return 0; }

2.8判断链表是否有环路，获取连接点，计算环的长度

此题很有意思，

判断是否含有环：slow和fast，slow指针每次走一步，fast指针每次走两步，若是链表有环，fast必能追上slow（相撞），若fast走到NULL，则不含有环。

//判断是否含有环 bool containLoop(Node* head){
    if (head==NULL) {
    return false; } Node* slow = head; Node* fast = head; while (slow!=fast&&fast->next!=NULL) {
    slow = slow->next; fast = fast->next->next; } if (fast==NULL) {
    return false; } return true; }

判断环的长度：在相撞点处，slow和fast继续走，当再次相撞时，slow走了length步，fast走了2length步，length即为环得长度。

//获得环的长度 int getLoopLength(Node head){
    if (head==NULL) {
    return 0; } Node* slow = head; Node* fast = head; while (slow!=fast&&fast->next!=NULL) {
    slow = slow->next; fast = fast->next->next; } if (fast==NULL) {
    return 0; } //slow和fast首次相遇后，slow和fast继续走 //再次相遇时，即slow走了一圈，fast走了两圈 int length = 0; while (slow!=fast) {
    length++; slow = slow->next; fast = fast->next->next; } return length; }

环得连接点：slow和fast第一次碰撞点到环的连接点的距离=头指针到环的连接点的距离，此式可以证明，详见上面链接。

//获得环的连接点 Node* getJoinpoit(Node* head){
    if (head==NULL) {
    return NULL; } Node* slow = head; Node* fast = head; while (slow!=fast&&fast->next!=NULL) {
    slow = slow->next; fast = fast->next->next; } if (fast==NULL) {
    return NULL; } Node* fromhead = head; Node* fromcrashpoint = slow;

while (fromcrashpoint!=fromhead) {    fromhead = fromhead->next;    fromcrashpoint = fromcrashpoint->next;}return fromhead;

}

2.9二叉树和双向链表转化

二叉树和双向链表转化指的是，二叉树节点结构和双向链表的结构想类似，只不过二叉树节点的节点存储的两个指针为左右子数，而双向链表存储的是前后节点。题意为将二叉树的某种遍历转化为链表存储。此题很明显该用递归，读者可以画图体会一下指针变化。

二叉树节点或双向链表节点定义：

struct BinaryTreeNode{
    int value; BinaryTreeNode* left; BinaryTreeNode* right; };

二叉树的中序遍历转换为双向链表

BinaryTreeNode* convertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInLast){
    if (pNode == NULL) {
    return NULL; } BinaryTreeNode *pCurrent = pNode; if (pCurrent->left != NULL) {
    convertNode(pCurrent->left, pLastNodeInLast); }

pCurrent->left = *pLastNodeInLast;if (*pLastNodeInLast != NULL) {    (*pLastNodeInLast)->right=pCurrent;}*pLastNodeInLast = pCurrent;if (pCurrent->right != NULL) {    convertNode(pCurrent->right, pLastNodeInLast);}return NULL;

}

BinaryTreeNode* convertBTToDLL(BinaryTreeNode* root){

      
 BinaryTreeNode pLastNodeInLast = NULL;
 convertNode(root, &pLastNodeInLast);
 BinaryTreeNode pHeadOfList = pLastNodeInLast;
while (pHeadOfList != NULL && pHeadOfList->left != NULL) { 
      
 pHeadOfList = pHeadOfList->left;
 }
return pHeadOfList;
 }