/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
//双指针，同步走，统计步数差，让慢一步的指针从头先走此步数差，然后两指针同时开始走，相等时，为相交点，走到头不相等，则不想交。
ListNode *node1=headA,*node2=headB;
int stepA=0,stepB=0;
while(node1!=nullptr)
{
stepA++;
node1=node1->next;
}
while(node2!=nullptr)
{
stepB++;
node2=node2->next;
}
node1=headA;
node2=headB;
int k=(stepA>=stepB)?stepA-stepB:stepB-stepA;
while(stepA>stepB&&k--) node1=node1->next;
while(stepA<stepB&&k--) node2=node2->next;
while(node1!=node2)
{
node1=node1->next;
node2=node2->next;
}
if(node1==nullptr)return nullptr;
return node1;
}
};
class Solution {
public:
int majorityElement(vector<int>& nums) {
//法一借助字典结构，统计数目；法二类似于消消乐，两个数目不同，count减一，相同加一
/* unordered_map<int,int>mmap;
int maxnum=0,value=nums[0];
for(auto x:nums)
{
auto iter=mmap.find(x);
if(iter==mmap.end())
{
mmap.insert(pair<int,int>(x,1));
}
else{
iter->second++;
if(iter->second>maxnum){
value=iter->first;
maxnum=iter->second;
}
}
}
return value;
*/
int count=0;
int cand;
for(auto x:nums)
{
if(count==0)
{ cand=x;
count++;
}
else{
if(x!=cand)count--;
else count++;
}
}
return cand;
}
};
//三个方法，法一，借助栈，时间和空间复杂度都是O(n),直接改变得节点值；法二法三，递归法和迭代法，改变next指针走向。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* h;
ListNode* reverseList(ListNode* head) {
//法一：栈，时间复杂度O(n),空间复杂度O(n)
/* stack<int>st;
ListNode*p=head;
while(p!=nullptr)
{
st.push(p->val);
p=p->next;
}
p=head;
while(p!=nullptr)
{
p->val=st.top();
st.pop();
p=p->next;
}
return head;
*/
//递归法
/* if(head==nullptr||head->next==nullptr)
return head;
ListNode*h=reverseList(head->next);
head->next->next=head;
head->next=nullptr;
return h;//每次传递的都是原末位节点；
*/
//迭代法
if(head==nullptr||head->next==nullptr)
return head;
ListNode*pre=head,*cur=head->next,*next;
while(cur!=nullptr)
{
next=cur->next;
cur->next=pre;
pre=cur;
cur=next;
}
head->next=nullptr;
return pre;
}
};
