给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的。
进阶:
你能尝试使用一趟扫描实现吗?
先遍历一遍计算链表长度;再遍历一遍删除倒数第n个节点
只遍历一遍链表,能否解决这个问题?
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
assert(n >= 0);
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* p = dummyHead;
ListNode* q = dummyHead;
for (int i = 0; i < n + 1; i++)
{
assert(q);
q = q -> next;
}
while ( q != NULL)
{
p = p -> next;
q = q -> next;
}
ListNode* delNode = p -> next;
p -> next = delNode -> next;
delete delNode;
ListNode* retNode = dummyHead->next;
delete dummyHead;
return retNode;
}
};
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶: 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?
class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode* slowp = head;
ListNode* fastp = head;
ListNode* revp = NULL;
while (fastp && fastp->next) {
fastp = fastp->next->next;
ListNode* tmp = slowp->next;
slowp->next = revp;
revp = slowp;
slowp = tmp;
}
if (fastp)
slowp = slowp->next;
while ( slowp && revp) {
if (slowp->val != revp->val) return false;
slowp = slowp->next;
revp = revp->next;
}
return true;
}
};