实现链表的反转有两个方法:
(1)定义一个新的链表,实现链表反转,但是会造成内存空间的浪费;
(2)只需要改变next指针的方向,就可以直接对链表反转,如下面动画所示:
步骤如下:
1.使cur指针指向现在的头结点;
2.初始化一个pre指针,初始化为null;
3.将cur->next用tmp存一下,改变next的方向(使用循环),最后cur指向null,返回pre为新的头结点。
//Solution 1 --双指针法
ListNode* reverseList(ListNode* head) {
ListNode* cur = head;
ListNode* pre = NULL;
while(cur != NULL) {
ListNode* tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
可以使用递归法实现:
//Solution 2 --递归法
ListNode* reverseList(ListNode* head) {
return reverse(NULL,head);
}
ListNode* reverse(ListNode* pre,ListNode* cur) {
if (cur == NULL) {
return pre;
}
ListNode* tmp = cur->next;
cur->next = pre;
return(cur,tmp)
}
版权声明:本文为qq_43697646原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。