删除链表中的节点
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。
现有一个链表 -- head = [4,5,1,9]，它可以表示为:
4 -> 5 -> 1 -> 9
示例 1:
输入: head = [4,5,1,9], node = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:
输入: head = [4,5,1,9], node = 1 输出: [4,5,9] 解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
说明:
- 链表至少包含两个节点。
- 链表中所有节点的值都是唯一的。
- 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
- 不要从你的函数中返回任何结果。
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* temp1=head;ListNode* temp2=head;int m=n-1;if(head->next==NULL)return head->next;while(m--){temp1=temp1->next;}while(temp1->next!=NULL&& temp1->next->next!=NULL){temp1=temp1->next;temp2=temp2->next;}if(temp1->next==NULL){temp2->val=temp2->next->val;// cout<<" b="<<temp2->next->val;temp2->next=temp2->next->next;// cout<<" af="<<temp2->next->val;return head;}if(temp2->next->next==NULL){temp2->next=NULL;return head;}// temp2->val=temp2->next->val;temp2->next=temp2->next->next;return head;}
};
反转链表
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* node1=head;ListNode* node2=head;if(head==NULL||head->next==NULL)return head;vector<int> out;while(node1!=NULL){out.push_back(node1->val);node1=node1->next;}for(int i=out.size()-1;i>=0;i--){node2->val=out[i];node2=node2->next;}return head;}
};回文链表
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false示例 2:
输入: 1->2->2->1 输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
class Solution {
public:bool isPalindrome(ListNode* head) {if(head==NULL||head->next==NULL)return true;int num=0;ListNode* node1=head;ListNode* node=head;while(node1!=NULL){num++;node1=node1->next;}// cout<<"num="<<num;int i=0;while(i<num/2){int l= num-i;ListNode* node2=node;while(--l){node2=node2->next; }// cout<<",head="<<head->val<<"node2="<<node2->val;if(head->val!=node2->val)return false;elsehead=head->next;i++;// cout<<",i="<<i;}return true;}
};