先把单链表构建起来
链表的结点结构体：
struct node{ int value; node *next; }; typedef node*Node;
单链表的初始化
Node init(){ Node head = NULL; Node p = NULL; int tmp; cin>>tmp; head = new node; head->value = tmp; head->next = NULL; p = head; while(cin>>tmp){ Node s = new node; s->value = tmp; s->next = NULL; p->next = s; p=s; } return head; }
单链表的打印
void printList(Node head){ if(head == NULL){ return; } Node p = head; while(p != NULL){ cout<<p->value<<" "; p = p->next; } }
单链表释放结点(C++没有垃圾回收机制-->不然会导致内存泄漏)
void delList(Node head){ Node p = head->next; while(p!=NULL){ delete head; head = p; p = p->next; } delete head; head = NULL; }
好了，let's
==>面题1
反转单链表
/* * 通过三个指针来完成, * pre用于指向前一个 * next用于指向下一个 * head用于指向要换指向的那一个 * */ Node reverseLinkedList(Node head){ Node pre = NULL; Node next = NULL; while(head != NULL){ next = head->next; head->next = pre; pre = head; head = next; } return pre; }
==>面题2
删除单链表中的某个值
Node removeValue(Node head,int elem){ Node s = NULL; //先处理头部是elem的元素 while(head != NULL){ if(head->value != elem){ break; } s = head; head = head->next; delete s; s = NULL; } //处理有elem的结点 Node p = head; Node cur = head; while(cur != NULL){ if(cur->value == elem){ s = cur; p->next = cur->next; cur = cur->next; delete s; s = NULL; }else{ p = cur; cur = cur->next; } } return head; }
主函数
int main() { Node head = NULL; head = init(); printList(head); cout<<endl; //???? head = reverseLinkedList(head); printList(head); cout<<endl; //??????? head = removeValue(head,3); printList(head); delList(head); system("pause"); return 0; }
