链表

203. 移除链表元素

设置一个虚拟头结点,不需要考虑头结点和非头结点的不同处理方式

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head;

        ListNode* cur = dummyHead;
        while(cur->next != nullptr) {
            if(cur->next->val == val) {
                // 相等就一直删除
                ListNode* temp = cur->next;
                cur->next = cur->next->next;
                delete temp;
            } else {
                // 不等就进入下一个
                cur = cur->next;
            }

        }
        head = dummyHead->next;
        delete dummyHead;
        return head;
    }
};

707. 设计链表

class MyLinkedList {

public:
    struct LinkNode{
        int val;
        LinkNode* next;
        LinkNode(int val):val(val), next(nullptr){}
    };
    MyLinkedList() {
        _dummyHead = new LinkNode(0);
        _size = 0;
    }

    int get(int index) {
        if(index > _size-1 || index < 0) return -1;
        LinkNode* cur = _dummyHead->next;
        for(int i=0; i<index; i++){
            cur = cur->next;
        }
        return cur->val;
    }

    void addAtHead(int val) {
        LinkNode* node = new LinkNode(val);
        node->next = _dummyHead->next;
        _dummyHead->next = node;
        _size++;
    }

    void addAtTail(int val) {
        LinkNode* node = new LinkNode(val);
        LinkNode* cur = _dummyHead;
        while(cur->next != nullptr){
            cur = cur->next;
        } 
        cur-> next = node;
        _size++;
    }

    void addAtIndex(int index, int val) {
        if(index < 0) addAtHead(val);
        else if(index == _size) addAtTail(val);
        else if(index > _size) return;
        else {
            LinkNode* cur = _dummyHead;
            for(int i=0; i<index; i++) cur = cur->next;
            LinkNode* node = new LinkNode(val);
            node->next = cur->next;
            cur->next = node;
            _size++;
            }
    }

    void deleteAtIndex(int index) {
        if(index>=0 && index<_size) {
            LinkNode* cur = _dummyHead;
            for(int i=0; i<index; i++) cur = cur->next;
            LinkNode* temp = cur->next;
            cur->next = cur->next->next;
            delete temp;
            _size--;
        }

    }

private:
    int _size = 0;
    LinkNode* _dummyHead;
};

206. 反转链表

  • 前后指针

    class Solution {
    public:
      ListNode* reverseList(ListNode* head) {
          if(head==nullptr) return head;
          ListNode* cur = head;
          ListNode* pre = nullptr;
          // 当cur为空指针停止
          while(cur != nullptr) {
              ListNode* temp = cur->next;  // 保存cur的下一个节点
              cur->next = pre;
              pre = cur;
              cur = temp;
          }
          return pre;
      }
    };
  • 递归法

    class Solution {
    public:
      ListNode* reverseList(ListNode* head) {
          // 如果head为空 或者 只剩一下一个元素 就不需要反转了
          if (head == nullptr || head->next == nullptr) return head;
          // 递
          ListNode * p = reverseList(head->next);
          // 归
          // 反转
          head->next->next = head;
          head->next = nullptr;
    
          return p;
      }
    };
    
  • 使用栈

    class Solution {
    public:
      ListNode* reverseList(ListNode* head) {
          if(!head) return nullptr;
    
          stack stk;
    
          while(head) {
              stk.push(head);
              head = head->next;
          }
          head = stk.top();
          ListNode *cur = head;
          stk.pop();
    
          while(!stk.empty()) {
              cur->next = stk.top();
              cur = cur->next;
              stk.pop();
          }
          cur->next = nullptr;
    
          return head;
      }
    };
    

24. 两两交换链表中的节点

  • 迭代,根据奇偶得出循环条件,设置虚假头结点

    class Solution {
    public:
      ListNode* swapPairs(ListNode* head) {
          ListNode* dummyHead = new ListNode(0);
          dummyHead->next = head;
          ListNode* cur = dummyHead;
    
          while(cur->next!=nullptr && cur->next->next!=nullptr) {
              ListNode* cnnnt =  cur->next->next->next;
              ListNode* cnt = cur->next;
    
              cur->next = cur->next->next;
              cur->next->next = cnt;
              cur->next->next->next = cnnnt;
    
              cur = cur->next->next;
          }
          return dummyHead->next;
      }
    };
  • 递归

19. 删除链表的倒数第 N 个结点

  • 快慢指针

    class Solution {
    public:
      ListNode* removeNthFromEnd(ListNode* head, int n) {
          ListNode* dummyHead = new ListNode(0);
          dummyHead->next = head;
          ListNode* fast = dummyHead;
          ListNode* slow = dummyHead;
          for(int i=0;i<=n;i++)
              fast = fast->next;
    
          while(fast != nullptr) {
              fast = fast->next;
              slow = slow->next;
          }
          ListNode* delNode = slow->next;
          slow->next = slow->next->next;
          delete delNode;
    
          return dummyHead->next;
      }
    };

面试题 02.07. 链表相交

计算长度,得到差值,寻找相交

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lenA = 0, lenB = 0;
        ListNode* curA = headA, *curB = headB;
        while(curA != NULL) {
            lenA++;
            curA = curA->next;
        }
        while(curB != NULL) {
            lenB++;
            curB = curB->next;
        }
        curA = headA;
        curB = headB;

        // 让A为长的那个链表
        if(lenA < lenB) {
            swap(lenA, lenB);
            swap(curA, curB);
        }
        // 让A先前进
        int subLen = lenA - lenB;
        while(subLen) {
            subLen--;
            curA = curA->next;
        }
        while(curA !=NULL) {
            if(curA == curB) return curA;
            curA = curA->next;
            curB = curB->next;
        }
        return NULL;
    }
};

142. 环形链表 II

理论推导可以得出,从开始的地方走到环起点,和从相遇的地方走到环起点,是一样多的。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head, *slow = head;
        while(fast!=NULL && fast->next!=NULL) {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) {
                ListNode* index1 = head;  //头结点
                ListNode* index2 = fast;  //相遇的地方
                while(index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index1;
            }
        }
        // 否则就是不存在环
        return NULL;
    }
};
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇