2019-02-18 leetcode
2019-02-18 本文已影响0人
昸北
今日三道关于链表的题目(基础):
1.合并两个有序链表:
合并链表是比较基础的题目了,主要就是几种情况:
--l1和l2有一个为空,则返回另一个。
--l1和l2均不为空,则挨个比较,每次连小的,并移动相应的指针。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1==nullptr){
return l2;
}
if(l2==nullptr){
return l1;
}
ListNode* res = nullptr;
if(l1->val <= l2->val){
res = l1;
l1 = l1->next;
}
else{
res = l2;
l2 = l2->next;
}
ListNode* head = res;
while(l1!=nullptr && l2!=nullptr){
if(l1->val <= l2->val){
head->next = l1;
head = head->next;
l1 = l1->next;
}
else{
head->next = l2;
head = head->next;
l2 = l2->next;
}
}
head->next = l1 != nullptr ? l1: l2;
return res;
}
};
2.回文链表
回文链表的题目有进阶要求,显然我没达到。
我的想法就是,遍历链表,将其存在数组中,然后采用判断回文的方法进行判断。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
vector<int>s;
while(head!=nullptr){
s.push_back(head->val);
head = head->next;
}
if(isPalindrome(s) == true){
return true;
}
else{
return false;
}
}
bool isPalindrome(vector<int>s) {
int len = s.size();
for(int i=0, j=len-1; i<len/2,j>=i; ){
if(s[i] == s[j]){
i++;
j--;
continue;
}
else{
return false;
}
}
return true;
}
};
3.环形链表
这个解法,快慢指针还是第一次看见。
参考博客:使用快慢指针的方法,设定两个指针,如果快指针追上慢指针则有环,如果指向了NULL则无环。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head==NULL)
{
return false;
}
ListNode* fast=head;
ListNode* slow=head;
while(fast->next && fast->next->next)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
return true;
}
}
return false;
}
};