单链表相关面试题总结

主要来自于《剑指offer》，都是面试高频题

1. 删除结点

删除节点需要知道上一个节点的地址。就需要遍历，可以把问题转化为删除下一个节点，把下一个节点的值拷贝给本节点。

删除pdel就转化为删除pnext,不需要再从头遍历。时间复杂度为O（1）.但是pdel为尾节点或者头节点需要另外的处理。

typedef struct SignalListNode {SignalListNode(const int& data = 0):_data(data),_Pnext(NULL){}SignalListNode *_Pnext;int _data;
}Node;void DeleteNode(Node *&phead, Node *delNode) //删除节点
{if (NULL == phead || NULL == delNode)return;if (delNode->_Pnext != NULL) //非尾节点{Node *pnext = delNode->_Pnext;delNode->_data = pnext->_data;delNode->_Pnext = pnext->_Pnext;delete pnext;pnext = NULL;}else if (phead == delNode)  //头节点{delete delNode;delNode = NULL;phead = NULL;}else  //尾节点{Node* ptemp = phead;while (ptemp -> _Pnext != delNode){ptemp = ptemp->_Pnext;}ptemp->_Pnext = NULL;delete delNode;delNode = NULL;}}

2.逆序打印

每次将节点入栈，然后出栈打印，栈和递归可以转化

void PrintTailtoHead_Nor(Node *phead)
{stack st;while (phead){st.push(phead);phead = phead->_Pnext;}while (!st.empty()){Node* pTemp = st.top();cout << pTemp->_data << "->";st.pop();}cout << "NULL" << endl;
}void PrintTailToHead(Node *phead)
{if (phead){PrintTailToHead(phead->_Pnext);cout << phead->_data << "->";}
}

3.删除倒数第K个节点

用快慢指针的方法，让快的先走K-1步，然后让快慢指针同时走，快指针到头时，慢指针到第倒数K个节点。

Node* FindKToTail(Node *phead, size_t k) //删除倒数第K个节点
{if (NULL == phead || k == 0)return NULL;Node *fast = phead;Node *slow = phead;while (--k){if (fast->_Pnext == NULL){cout << "已经到头了" << endl;return NULL;}fast = fast->_Pnext;}while (fast->_Pnext != NULL){slow = slow->_Pnext;fast = fast->_Pnext;}return slow;
}

4.翻转单链表

用ppre,pnode,pnext分别标记前一个，当前节点，后一个节点，在处理时需要注意顺序，和空指针的判断

Node* ResverLsit(Node *phead)   //翻转链表
{if (NULL == phead || phead->_Pnext == NULL)return phead;Node* Tailhead = NULL;Node *pnode = phead;Node *ppre = NULL;while (pnode != NULL){Node *pnext = pnode->_Pnext;if (NULL == pnext)Tailhead = pnode;pnode->_Pnext = ppre;ppre = pnode;pnode = pnext;      }return Tailhead;
}

5.合并两个有序链表

//合并两个有序链表
Node *MergeList(Node *phead1, Node* phead2)
{if (NULL == phead1)return phead2;if (NULL == phead2)return phead1;Node* newhead = NULL;if (phead1->_data < phead2->_data){newhead = phead1;newhead->_Pnext = MergeList(phead1->_Pnext, phead2);}else {newhead = phead2;newhead->_Pnext = MergeList(phead1, phead2->_Pnext);}return newhead;
}

6.求两个链表的第一个交点（不带环）

和第三题一样使用快慢指针的方法，先求出两个链表的长度，让长的先走它们的差值步。然后一起走，第一个相遇的节点就是两个链表的第一个交点。

size_t  GetlenghtList(Node* phead)
{if (NULL == phead)return 0;Node* pNode = phead;while (pNode->_Pnext != NULL)pNode = pNode->_Pnext;return (pNode - phead + 1);
}Node* FindFirstFcous(Node* phead1, Node* phead2)
{size_t len1 = GetlenghtList(phead1);size_t len2 = GetlenghtList(phead2);int len = len1 - len2;Node* shorthead = phead2;Node* longhead = phead1;if (len1 < len2){shorthead = phead1;longhead = phead2;len = len2 - len1;}for (int i = 0; i < len; ++i)longhead = longhead->_Pnext;while ((longhead != NULL) &&(shorthead != NULL) &&(longhead != shorthead)){longhead = longhead->_Pnext;shorthead = shorthead->_Pnext;}return longhead;
}

7.约瑟夫环问题

一种是自己构建环，或者使用STL容器。

//约瑟夫环问题，0-n-1构成环，每次删除第m个元素，求最后剩下的数字
int JosephRing_1(int n, int m)
{if (n < 1 || m < 1)return -1;Node* Ring = NULL;for (int i = 0; i < n; ++i)PushBack(Ring, i);Node* Tail = TailNode(Ring);Tail->_Pnext = Ring;Node* ppre = Tail;Node* pnode = Ring;while (ppre != pnode){for (int j = 1; j < m; ++j){ppre = ppre->_Pnext;pnode = pnode->_Pnext;}Node *pdel = pnode;ppre->_Pnext = pnode->_Pnext;pnode = pnode->_Pnext;delete pdel;}return pnode->_data;
}int JosephRing_2(int n, int m)
{if (n < 1 || m < 1)return -1;list<int> ring;for (int i = 0; i < n; ++i)ring.push_back(i);list<int>::iterator it = ring.begin();while (ring.size() > 1){for (int j = 1; j < m; ++j){++it;if (it == ring.end())it = ring.begin();}list<int>::iterator next = ++it;if (next == ring.end())next = ring.begin();--it;ring.erase(it);it = next;}return (*it);
}

8.判断链表是否带环，如果带环，求入口点。

和3，6题一样用到快慢指针，慢指针每次走一步，快指针每次走两步。如果带环，它们一定会在环内相遇。
入口点：先求出环的节点个数（走一圈），让快的先走一圈的个数步，然后两个同时走，会在入口点相遇。

//判断是否带环
Node *MeetingNode(Node* phead)
{if (NULL == phead)return phead;Node *slow = phead->_Pnext;if (NULL == slow)return NULL;Node *fast = phead->_Pnext;while (fast != NULL && slow != NULL){if (slow == fast)return fast;slow = slow->_Pnext;if (fast->_Pnext != NULL)fast = fast->_Pnext->_Pnext;elsereturn NULL;}return NULL;
}
//求入口点
Node *GetEnterNode(Node *phead)
{Node *meetNode = MeetingNode(phead);if (NULL == meetNode)return NULL;int ringnode = 1;Node *pnode = meetNode->_Pnext;while (pnode != meetNode){++ringnode;pnode = pnode->_Pnext;}Node* fast = phead;Node* slow = phead;for (int i = 0; i < ringnode; ++i){fast = fast->_Pnext;}while (fast != slow){fast = fast->_Pnext;slow = slow->_Pnext;}return slow;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！