leetcode单向链表[206, 24, 141, 142, 25]

【leetcode】链表题目训练[206, 24, 141, 142, 25]

题目一：206. Reverse Linked List

​ 题目：Reverse a singly linked list.

• 理解：反转一个单项链表
• 难度：easy

解法：

• 思路：头节点开始依次往后遍历链表，并更改每一个节点的next指针为前一个结点的地址
• 代码

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL) return head;
        ListNode *cur = head, *prev = NULL, *lat = head->next;
        while(cur){
        	cur->next = prev;
        	prev = cur;
        	cur = lat;
        	if(lat != NULL) lat = lat->next;
		}
        return prev;
    }
};

题目二：24. Swap Nodes in Pairs

​ 题目：Given a linked list, swap every two adjacent nodes and return its head.You may not modify the values in the list’s nodes, only nodes itself may be changed.

• 理解：从第一个节点开始，依次反转两个相邻的节点
• 难度：medium

解法：

• 思路：两个节点一组，将第二个指向第一个，然后将第一个指向下一组的第二个，如此循环，如下图

• 代码

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head == NULL || head->next == NULL) return head;
        ListNode *cur = head->next, *temp = cur->next, *prev = head, *res = head->next;
        while(true){
            temp = cur->next;
            cur->next = prev;
            if(temp == NULL || temp->next == NULL){
                prev->next = temp;
                return res;
            }
            cur = temp->next;
            prev->next = cur;
            prev = temp;
        }
    }
};

题目三：141. Linked List Cycle

​ 题目：Given a linked list, determine if it has a cycle in it.To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1,then there is no cycle in the linked list.

• 理解：判断一个链表是否有环
• 难度：easy

解法一：

• 思路：快慢指针，创建两个指针，一个指针每次遍历两个节点，一个每次遍历一个节点，当遇到NULL则返回无环，当两个指针相遇则返回有环
  • 缺点：时间复杂度大于O(n)

• 代码：

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *cur = head, *prev = head, *temp = head;
        while(cur){
            if(!cur->next || !(cur->next)->next){
                return false;
            }
            prev = prev->next;
            cur = (cur->next)->next;
            if(cur == prev){
                return true;
            }
        }
        return false;
    }
};

解法二：

• 思路：遍历一遍，将遍历到的节点指向head，遍历过程中遇到NULL则返回无环，遍历过程中遇到head则返回有环
  • 优点：时间复杂度O(n)
  • 缺点：更改了原有的链表

• 代码：

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *cur = head, *prev = head;
        while(cur){
            if(cur->next == head){
                return true;
            }
            prev = cur->next;
            cur->next = head;
            cur = prev;
        }
        return false;
    }
};

题目四：142. Linked List Cycle II

​ 题目：Given a linked list, return the node where the cycle begins. If there is no cycle, return null.To representa cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in thelinked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

​ Note: Do not modify the linked list.

• 理解：141题的hard，在判定有环的基础上返回尾部所指向的节点
• 难度：medium

解法：

• 思路：创建一个unordered_set，然后依次遍历，将遍历到的节点的地址存放到unordered_set，然后判断当前节点的next存放的地址是否在unordered_set中存在，存在的话，则返回该地址。
• 代码：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == NULL || head->next == NULL) return NULL;
        ListNode *cur = head;
        unordered_set<ListNode*> se;
        while(cur->next){
            if(se.find(cur) == se.end()){
                se.insert(cur);
                cur = cur->next;
            }
            else{
                return *se.find(cur);
            }
        }
        return NULL;
    }
};

题目五：25. Reverse Nodes in k-Group

​ 题目：Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k thenleft-out nodes in the end should remain as it is.

• 理解：24题的hard，原先是反转相邻两个节点的基础上，现在是反转k个节点
• 难度：hard

解法

• 思路：基本思路和24题相同
• 代码：

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(head == NULL || head->next == NULL || k == 1) return head;
        
        ListNode *test = head, *res = NULL, *cur = head, *prev = NULL, *lat = head, *temp = head;
        int n = k, i = 0;
        while(true){
            n = k;
            i++;
            while(test && n){
            	n -= 1; 
                if(n + 1 == k) test = cur;
                else test = test->next;
            }
            
            if(!n && test){
                n = k;
               
                if(i >= 2){
                	temp->next = test;
                	temp = cur;
				} 
                if(!res) res = test;
                while(n--){
                    lat = lat->next;
                    cur->next = prev;
                    prev = cur;
                    cur = lat;
                }
            }
            else if(i == 1){
            	return head;
			}
            else{
                temp->next = cur;
                return res;
            }
        }
    }
};