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

0.摘要

• 定义


• 插入节点（单向链表）


• 删除节点（单向链表）


• 反向遍历链表


• 找出中间节点


• 找出倒数第k个节点


• 翻转链表


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


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


• 二叉树和双向链表转化

1.定义

1.1单向链表

单向链表的节点包括：

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



2. 指针域（链域）：用于存储下一个结点地址或者说指向其直接后继结点的指针。

   
   

    struct Node{
   
   int value;
   
   Node * next;
   
   };

1.2双向链表

双向链表的节点包括：

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


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



3. 右指针域（右链域）：用于存储下一个结点地址或者说指向其直接后继结点的指针。

   
   

    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;

}

//1.stack

void printLinkedListReversinglyByStack(Node head){

stack<Node* > 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);

}

}

//找出中间节点

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判断链表是否有环路，获取连接点，计算环的长度

此题很有意思，具体详细请参考：http://www.cnblogs.com/xudong-bupt/p/3667729.html

判断是否含有环：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;

<span class="hljs-keyword">while</span> (fromcrashpoint!=fromhead) {
    fromhead = fromhead-&gt;next;
    fromcrashpoint = fromcrashpoint-&gt;next;
}
<span class="hljs-keyword">return</span> 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;
<span class="hljs-keyword">if</span> (*pLastNodeInLast != <span class="hljs-keyword">NULL</span>) {
    (*pLastNodeInLast)-&gt;right=pCurrent;
}

*pLastNodeInLast = pCurrent;
<span class="hljs-keyword">if</span> (pCurrent-&gt;right != <span class="hljs-keyword">NULL</span>) {
    convertNode(pCurrent-&gt;right, pLastNodeInLast);
}
<span class="hljs-keyword">return</span> <span class="hljs-keyword">NULL</span>;
}
BinaryTreeNode* convertBTToDLL(BinaryTreeNode* root){

BinaryTreeNode pLastNodeInLast = NULL;

convertNode(root, &pLastNodeInLast);

BinaryTreeNode pHeadOfList = pLastNodeInLast;

while (pHeadOfList != NULL && pHeadOfList->left != NULL) {

pHeadOfList = pHeadOfList->left;

}

return pHeadOfList;

}