C/C++面试(4)——链表操作

1.不带头结点的链表逆序

2.给任意一个结点，在不遍历链表的情况下，删除该节点

`#include<iostream>#include<stdlib.h>#include<time.h>using namespace std;typedef struct node{ int value; struct node* next;}Node;Node* Reverse(Node* head)//但是当时机试题给的接口是void Reverse(Node* head)，这个我就真心想不出来，因为head=p2，程序就死了。{/*非递归解法 if (head == NULL || head -> next == NULL) return head; Node * p1 = head, *p2 = head -> next, *p3 = NULL; p1 -> next = NULL; while ((p3 = p2 -> next) != NULL){ p2 -> next = p1; p1 = p2; p2 = p3; } p2 -> next = p1; head = p2; return head;*/ //递归 if (head == NULL || head -> next == NULL) return head; Node * tail = head -> next; Node * newhead = Reverse(head -> next); tail -> next = head; head -> next = NULL; return newhead;}void display(Node* head){ Node * cur = head; while (cur){ cout << cur -> value << ' '; cur = cur -> next; } cout << endl;}void deleteNode(Node * p){ Node * nextP = p -> next; p -> value = nextP -> value; //复制下一个结点 p -> next = nextP -> next; delete nextP; //删除下一个结点}int main(){ int n; cin >> n; Node * head = NULL, *cur = NULL, *pre = NULL; for (int i = 1; i <= n; i ++){ if (head == NULL){ head = new Node; head -> value = i; head -> next = NULL; pre = head; //cur = pre -> next; } else{ cur = new Node; cur -> value = i; cur -> next = NULL; pre -> next = cur; pre = cur; //cur = cur -> next; } //cur = pre -> next; } cur -> next = NULL; head = Reverse(head); cout << "Reverse:"; display(head); cur = head; srand(time(NULL)); int k = rand() % n; for (i = 1; i <= k && cur; i ++) cur = cur -> next; deleteNode(cur); cout << "delete NO." << k << " node :/n"; display(head); return 0;}`

Top