单链表相关面试题总结

主要来自于《剑指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<Node*> 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; else return 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; }