- 思路
- 方法1:头插法
- 方法2:递归
- 代码
- 头插法
ret为返回链表的头部
head_last指向下一个加入ret的节点
每次将head取出使用头插法将其插入ret
然后head=head_last, head_last=head->next
如此循环直至head_last为NULL
举例:
head_last: 2 -> 3
head: 1 #将head插入ret链表
ret: 1
head: 2 -> 3
head_last: 3
head: 2 #将head插入ret链表
ret: 2 -> 1
head: 3
head_last: NULL
head: 3 #将head插入ret链表
ret: 3 -> 2 -> 1
head_last: NULL跳出循环
方法2:递归使用递归,递归到head链表尾部,随着每一层递归的返回记录当前的head节点到新链表中,最后也能达到反转链表的效果
举例:
第一层:
head: 1 -> 2 -> 3
head->next 不为空
继续递归
第二层:
head: 2 -> 3
head->next 不为空
继续递归
第三层:
head: 3
head->next 为空
返回将当前节点加入新链表(ret = 3 -> NULL)
返回第二层:
返回将当前节点加入新链表(ret = 3 -> 2 -> NULL)
返回第一层:
返回将当前节点加入新链表(ret = 3 -> 2 -> 1 -> NULL)
struct ListNode* reverseList(struct ListNode* head){
struct ListNode *ret,*head_last;
while(head != NULL){
head_last = head->next;
head->next = ret;
ret = head;
if(head_last == NULL) break;
head = head_last;
}
return ret;
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)