首页 > 代码库 > 单链表反转问题
单链表反转问题
要求，给定一个单链表，要求对改单链表实现反转，即最后一个结点变成头结点
单链表定义和建立：
1 typedef struct Node 2 { 3 int data; 4 Node * pNext; 5 }Node,*LinkList; 6 7 void CreateListHead(Node **L, int n) 8 { 9 Node* p;10 int i;11 12 *L = (Node*)malloc(sizeof(Node));13 (*L)->pNext = NULL;14 15 for( i=0; i < n; i++ )16 {17 p = (Node*)malloc(sizeof(Node)); // 生成新结点18 p->data = http://www.mamicode.com/n-i;19 p->pNext = (*L)->pNext;20 (*L)->pNext = p;21 }22 }
迭代实现思路：
1 Node* ReverseLink(Node **head) 2 { 3 Node *next; 4 Node *prev = NULL; 5 6 while((*head) != NULL) 7 { 8 next = (*head)->pNext; 9 (*head)->pNext = prev;10 prev = (*head);11 (*head) = next;12 }13 14 return prev;15 }
递归实现：
整个递归中，newhead经过不断递归调用，最终指向到了最后一个结点，也就是我们需要返回的链表的新头结点，然后，head指针在递归完成后，要做回溯工作，即反转方向。因为外层利用了堆栈存下了前面的结点和指向，所以递归完成后，外层一定有一个指针还指着head，这也是递归可以比迭代少用一个变量的原因）
1 Node *ReverseLink2(Node **head) 2 { 3 Node *newHead; 4 5 if((*head)->pNext == NULL) 6 return (*head); 7 8 newHead = ReverseLink2(&(*head)->pNext); /*递归部分*/ 9 (*head)->pNext->pNext = (*head); /*回朔部分，把head的下个节点指向自己，head节点指为NULL*/10 (*head)->pNext = NULL;11 12 return newHead;13 }
单链表反转问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。