给定一个单链表的头结点pHead(该头节点是有值的,比如在下图,它的val是1),长度为n,反转该链表后,返回新链表的表头。
数据范围:
要求:空间复杂度 ,时间复杂度 。
如当输入链表{1,2,3}时,
经反转后,原链表变为{3,2,1},所以对应的输出为{3,2,1}。
以上转换过程如下图所示:
{1,2,3}
{3,2,1}
{}
{}
空链表则输出空
容易理解的/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ struct ListNode* ReverseList(struct ListNode* head ) { // write code here struct ListNode* p1,*p2; if(head == NULL || head ->next == NULL){ return head; }else{ p1 = head; p2 = head->next; head = p2->next; p2->next = p1; p1->next =NULL; while(head!=NULL){ p1 = p2; p2 = head; head = p2->next; p2->next = p1; } return p2; } }
struct ListNode* ReverseList(struct ListNode* head ) { //空链表与只有一个结点的链表都无需进行操作 if(head == NULL || head->next == NULL) { return head; } struct ListNode* pcur = head; struct ListNode* prev = NULL; struct ListNode* pnext = head; //反转链表,将后驱指针更新为前驱指针 while(pcur != NULL) { pnext = pcur->next; pcur->next = prev; prev = pcur; pcur = pnext; } return prev; }
我这为啥会报错误啊?大佬们 /** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ struct ListNode* ReverseList(struct ListNode* head ) { // write code here struct ListNode* pre, *end, *p; int num = 0; if (head == NULL || head->next == NULL) {//若只有一个元素或者空链表,直接返回 return head;; } pre = head; while (pre->next->next != NULL) { pre = pre->next;//将pre指针指向倒数第二个元素 } end = pre->next;//end指针指向最后一个元素 p = pre;//p指针指向倒数第二个元素 pre = head;//将pre指针指向第一个元素 while (pre != end) {//交换pre指针和end指针的数据域,p指针始终指向end指针指向元素的前驱节点 num = end->val; end->val = pre->val; pre->val = num; pre = pre->next; end = p; p = head; while (p->next != end) { p = p->next; } } return head; }
采用c语言双指针的方法 核心理解为:将链表的箭头反向调转,达到反转链表,即节点的指针指向前驱节点 struct ListNode* ReverseList(struct ListNode* head ) { // write code here struct ListNode* cur; struct ListNode* pre; struct ListNode* temp; if(head == NULL){ //如果为空链表,则输出为空链表 pre = NULL; }else{ cur = head;//初始化指向头节点 pre = NULL;//指向头节点的前一个节点,即NULL while(cur){ temp = cur->next;//保存后继节点 cur->next = pre;//指向前驱节点 pre = cur;//pre向后移动一节点 cur = temp;//cur向后移动一节点 } } return pre;//返回反转后的头节点 }
struct ListNode* ReverseList(struct ListNode* head ) { // write code here struct ListNode* resu_list; struct ListNode* p; struct ListNode* temp; if(head == NULL){ resu_list = NULL; }else{ resu_list = head; p = head->next; resu_list->next = NULL; while(p != NULL){ temp = p->next; p->next = resu_list; resu_list = p; p = temp; } } return resu_list; }
#include <stdio.h> struct ListNode* ReverseList(struct ListNode* head ) { struct ListNode* temp,* temp2,*temp3,*temp4; if (head==NULL){ return head; } else { temp2=head->next; temp=head; while (temp2!=NULL){ temp3=temp2->next; temp4=temp2; temp2->next=temp; temp2=temp3; temp=temp4; } head->next=NULL; head=temp; return head; } }
注意值传递方式
struct ListNode* Reverse(struct ListNode* cur, struct ListNode* pre) { if (cur == NULL) return pre; struct ListNode* temp = NULL; temp = cur-> next; cur->next = pre; return Reverse(temp, cur); } struct ListNode* ReverseList(struct ListNode* head ) { return Reverse(head, NULL); }
struct ListNode* ReverseList(struct ListNode* head ) { struct ListNode* prev = NULL; struct ListNode* curr = head; struct ListNode* next = NULL; while (curr != NULL) { next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; }
这段代码使用三个指针prev、curr和next来迭代地将链表中的节点依次反转。prev指向已反转的部分链表的头节点,curr指向待反转的节点,next用于保存curr的下一个节点。
在每次迭代中,先将curr的下一个节点保存到next中,然后将curr的next指针指向prev,实现反转。之后,将prev指向curr,curr指向next,继续进行下一次迭代。
当迭代结束时,prev指向的节点就是反转后的链表的头节点,将其返回即可。
struct ListNode* ReverseList(struct ListNode* head ) { // write code here if (head == NULL) return NULL; else { struct ListNode* p = head; struct ListNode* pN = head->next; while (pN != NULL) { p->next = pN->next;//断开已反转节点和下一个要反转节点之间的联系 pN->next = head;//pN反转过后是头节点 head = pN; pN = p->next;//pN指向下一个要反转的节点 } return head; } }
struct ListNode* ReverseList(struct ListNode* head ) { // write code here if (head == NULL || head->next == NULL) { return head; } //保存上一个结点 struct ListNode* pre = NULL; //保存下一个结点 struct ListNode* next=NULL; //保存当前结点 struct ListNode* cur = head; while (cur != NULL) { //保存当前的下一个结点,方便当前节点后移 next = cur->next; //当前结点的下一结点保存前结点,pre->cur => cur->pre,反转实现 cur->next = pre; //前结点后移 pre = cur; //当前结点后移 cur = next; } return pre; }