Leetcode链表反转怎么做？能否详细解释一下？

本文共计472个文字，预计阅读时间需要2分钟。

力扣链接+方法一：经典的双指针问题，这里为了方便采用三指针+/* Definition for singly-linked list. */ struct ListNode { int val; struct ListNode *next; }; */ /struct ListNode* reverseList(struct ListNode* head) {

力扣链接

方法一:

经典的双指针问题,这里为了方便采用三指针

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head) { struct ListNode* n1,*n2,*n3; n1 = NULL; n2 = head; n3 = n2->next; if(head == NULL) { return NULL; } while(n2) { //翻转 n2->next = n1; //迭代 n1 = n2; n2 = n3; n3 = n3->next ; } return n1; }

如图第28行出现了null pointer (空指针),所以n3可能为空,只需判断n3是否为空,当然有时报错不一定准确,需要进一步分析.

改进后代码:

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head) { struct ListNode* n1,*n2,*n3; n1 = NULL; n2 = head; n3 = n2->next; if(head == NULL) { return NULL; } while(n2) { //翻转 n2->next = n1; //迭代 n1 = n2; n2 = n3; if(n3) { n3 = n3->next ; } } return n1; }

这里的报错就不准确了,最后输入的测试用例给出了出错的原因-----链表可能为空,同样的只需判断就行:

最终代码:

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head) { if(head == NULL) { return NULL; } struct ListNode* n1,*n2,*n3; n1 = NULL; n2 = head; n3 = n2->next; if(head == NULL) { return NULL; } while(n2) { //翻转 n2->next = n1; //迭代 n1 = n2; n2 = n3; if(n3) { n3 = n3->next ; } } return n1; }

---

方法二:

取节点头插到新链表

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head) { struct ListNode* cur,*newHead; cur = head; newHead = NULL; while(cur) { struct ListNode* next = cur->next; cur->next = newHead; newHead = cur; cur = next; } return newHead; }