DL_fan的博客：链表的一些leetcode题目+python(c++)

当前位置博文首页 > DL_fan的博客：链表的一些leetcode题目+python(c++)

DL_fan的博客：链表的一些leetcode题目+python(c++)

作者：[db:作者] 时间：2021-07-10 22:18

主要常见下面几个知识点:?

1-1.请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。

python:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val = node.next.val
        node.next = node.next.next

c++实现:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        node->next = node->next->next;
    }
};

1-2.删除排序链表中的重复元素

通过将结点的值与它之后的结点进行比较来确定它是否为重复结点。如果它是重复的，我们更改当前结点的 next 指针，以便它跳过下一个结点并直接指向下一个结点之后的结点。如果不是重复的，则节点进行下移。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        node = head
        while node and node.next:
            if node.val == node.next.val:
                node.next = node.next.next
            else:
                node = node.next
        return head

c++实现:

/**
 * 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* new_node;
    Solution(){};
    Solution(const Solution& sol){
        this->new_node = new ListNode(0, NULL);
        this->new_node = sol.new_node;
    }//深拷贝 堆区开辟空间重新赋值 解决释放内存的问题
    ListNode* deleteDuplicates(ListNode* head) {
        this->new_node = head;
        while(this->new_node && this->new_node->next){
            if(this->new_node->val == this->new_node->next->val){
                this->new_node->next = this->new_node->next->next;
            }
            else{
                this->new_node = this->new_node->next;
            }
        }
        return head;
    }
    virtual ~Solution(){
        if(this->new_node !=NULL){
            this->new_node = NULL;
        }
    }
};

1-3.删除排序链表中的重复元素 II

思路:通过while循环一直去掉重复的元素

python:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        dummy_head = ListNode(0, head)
        cur = dummy_head
        while cur.next and cur.next.next:
            if cur.next.val == cur.next.next.val:
                x = cur.next.val
                while cur.next and cur.next.val == x:
                    cur.next = cur.next.next
            else:
                cur = cur.next
        return dummy_head.next

c++实现:?

/**
 * 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* dummy_head;
    ListNode* cur_node;
    Solution(){};
    Solution(const Solution& sol){
        dummy_head = sol.dummy_head;
        cur_node = sol.cur_node;
    }
    ListNode* deleteDuplicates(ListNode* head) {
        dummy_head = new ListNode(0, head);
        cur_node = dummy_head;
        while(cur_node->next && cur_node->next->next){
            if(cur_node->next->val == cur_node->next->next->val){
                int x = cur_node->next->val;
                while(cur_node->next && cur_node->next->val == x){
                    cur_node->next = cur_node->next->next;
                }
            }
            else{
                cur_node = cur_node->next;
            }
        }
        return dummy_head->next;
    }
    virtual ~Solution(){
        if(dummy_head != NULL){
            delete dummy_head;
            dummy_head = NULL;
        }
        if(cur_node != NULL){
            cur_node = NULL;
        }
    }
};

1-4.删除链表的倒数第N个节点

思路：找到链表长度，通过在头结点补充一个节点找到要删除的节点的上一个节点，然后在进行删除

方法１：循环

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        length = 0 
        node = head
        #获取链表长度
        while node:
            length+=1
            node= node.next
        # print(length)

        curr_length = 0
        new_head = ListNode(0)
        new_head.next = head
        node2=new_head
        stop_length = length - n
        #循环走到要删除节点的前一个节点
        while stop_length:
            stop_length-=1
            node2 = node2.next
        #跳过要删除的节点即可
        node2.next = node2.next.next
        return new_head.next

方法２：递归

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def __init__(self):
        self.count = 0
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        if not head:            
            return head  
        
        head.next = self.removeNthFromEnd(head.next, n) # 递归调用
        self.count += 1 # 回溯时进行节点计数
        return head.next if self.count == n else head

方法3:双指针

fist 指针与second指针相隔n,这样first跑到尾部,second的下一个节点就是倒数第n个

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    # def __init__(self):
    #     self.count = 0
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        new_head =  ListNode(0)
        new_head.next = head
        first  = head
        second = new_head
        for i in range(n):
            first = first.next
        while first:
            first = first.next
            second = second.next
        second.next = second.next.next
        return new_head.next

c++实现:?

/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        ListNode* new_head = new ListNode(0);
        new_head ->next = head;
        ListNode* first = head;
        ListNode* second = new_head;
        for(int i=0;i<n;i++){
            first = first->next;
        }
        while(first){
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next;
        return new_head->next;
    }
};

1-5. 删除链表的节点

思路:双指针

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        if head is None:
            return head
        new_head = ListNode(0)
        new_head.next = head
        pre = new_head
        cur = head
        while cur.val != val:
            pre = cur
            cur = cur.next
        pre.next = cur.next
        return new_head.next

c++实现:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if(head == NULL){
            return NULL;
        }
        ListNode* new_head = new ListNode(0);
        new_head->next = head;
        ListNode* pre = new_head;
        ListNode* cur = head;
        while(cur->val != val){
            pre = cur;
            cur = cur->next;
        }
        pre->next = cur->next;
        return new_head->next;
    }
};

1-6.两两交换链表中的节点

思路:迭代法

python代码:?

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        new_head = ListNode(0)
        new_head.next = head
        temp = new_head
        while temp.next and temp.next.next:
            node1 = temp.next
            node2 = temp.next.next
            temp.next = node2
            node1.next = node2.next
            node2.next = node1
            temp = node1
        return new_head.next

c++实现:

/**
 * 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* swapPairs(ListNode* head) {
        ListNode* new_head = new ListNode(0);
        new_head->next = head;
        ListNode* temp = new_head;
        while(temp->next && temp->next->next){
            ListNode* head1 = temp->next;
            ListNode* head2 = temp->next->next;
            temp->next = head2;
            head1->next = head2->next;
            head2->next = head1;
            temp = head1;
        }
        return new_head->next;
    }
};

思路:递归法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        new_head = head.next
        head.next =  self.swapPairs(new_head.next)
        new_head.next = head
        return new_head

c++实现:?

/**
 * 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* swapPairs(ListNode* head) {
        if(head == nullptr || head->next == nullptr){
            return head;
        }
        ListNode* new_head;
        new_head = head->next;
        head->next = swapPairs(new_head->next);
        new_head->next = head;
        return new_head;
    }
};

2-1.反转链表

思路１：双指针?

class Solution(object):
	def reverseList(self, head):
		"""
		:type head: ListNode
		:rtype: ListNode
		"""
		# 申请两个节点，pre和 cur，pre指向None
		pre = None
		cur = head
		# 遍历链表，while循环里面的内容其实可以写成一行
		while cur:
			# 记录当前节点的下一个节点
			tmp = cur.next
			# 然后将当前节点指向pre
			cur.next = pre
			# pre和cur节点都前进一位
			pre = cur
			cur = tmp
		return pre

c++实现:

/**
 * 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* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* temp = head;
        while(head){
            temp = head->next;
            head->next = pre;
            pre = head;
            head = temp;
        }
        return pre;
    }
};

思路2.递归法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # pre = None
        # cur = head

        # while cur:
        #     node = cur.next
        #     cur.next = pre
        #     pre = cur
        #     cur = node
        # return pre
        if head is None or head.next is None:
            return head
        new_node = self.reverseList(head.next)
        print('head.val',head.val)
        head.next.next = head
        head.next = None
        return new_node

2-2:旋转链表

思路:

构成循环列表以后　找到移动的节点　在拆分

python:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if k == 0 or head is None or head.next is None:
            return head
        #计算链表长度
        cur = head        
        n = 1
        while cur.next:
            cur = cur.next
            n += 1
        # print('==n:', n)        
        add = n - k % n
        if add == n:#k是n的整数倍直接返回原节点
            return head
        cur.next = head #构成环
        while add:
            cur = cur.next
            add -= 1
        new_head = cur.next#找到移动后的开始节点
        cur.next = None#拆开
        return new_head

c++实现:

/**
 * 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* rotateRight(ListNode* head, int k) {
        if(k == 0 || head == nullptr || head->next == nullptr){
            return head;
        }
        int n = 1;//得到环长度
        ListNode* cur = head;
        while(cur->next){
            cur = cur->next;
            n++;
        }
        //找到移动的add长度
        int add = n - k % n;
        if(add == n){
            return head;
        }
        cur->next = head;//构成环
        while(add){
            cur = cur->next;
            add--;
        }
        ListNode* new_node = cur->next;
        cur->next = nullptr;//拆环
        return new_node;


    }
};

3-1.合并两个排序的链表

思路:引入一个指针头 python实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:

        head = ListNode(0)
        node = head

        while l1 and l2:
            if l1.val < l2.val:
                node.next = l1
                l1 = l1.next
            else:
                node.next = l2
                l2 = l2.next
            node = node.next
        if l1 is not None:
            node.next= l1
        if l2 is not None:
            node.next= l2
        return head.next

c++实现:

/**
 * 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) {
        ListNode* new_head = new ListNode(0);
        ListNode* node = new_head;

        while(l1!=NULL && l2 !=NULL){
            if(l1->val<l2->val){
                node->next = l1;
                l1 = l1->next;
            }
            else{
                node->next  = l2;
                l2 = l2->next;                
            }
            node = node->next;
        }

        if (l1!=NULL){
            node->next = l1;
        }
        if(l2!=NULL){
            node->next = l2;
        }
        return new_head->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* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == nullptr){
            return l2;
        }
        if(l2 == nullptr){
            return l1;
        }
        if(l1->val < l2->val){
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else{
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

3-2.合并K个升序链表

思路1:上一题合并两个变成for循环顺序合并

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwo(self, l1, l2):
        if l1 is None:
            return l2
        if l2 is None:
            return l1
        head = ListNode(0)
        node = head
        while l1 and l2:
            if l1.val <l2.val:
                node.next = l1
                l1 = l1.next
            else:
                node.next = l2
                l2 = l2.next
            node = node.next
        if l1:
            node.next = l1
        if l2:
            node.next = l2
        return head.next

    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        ans  = None
        for i in range(len(lists)):
            ans = self.mergeTwo(ans,lists[i])
        return ans

c++:

/**
 * 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* mergtwo(ListNode* l1, ListNode* l2){
        if(l1==nullptr){
            return l2;
        }
        if(l2==nullptr){
            return l1;
        }
        ListNode* new_head= new ListNode(0);
        ListNode* node = new_head;
        while(l1 && l2){
            if(l1->val<l2->val){
                node->next = l1;
                l1= l1->next;
            }
            else{
                node->next = l2;
                l2= l2->next;
            }
            node = node->next;
        }
        if(l1){
            node->next = l1;
        }
        if(l2){
            node->next = l2;
        }
        return new_head->next;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* res = nullptr;
        for (int i=0;i<lists.size();i++){
            res = mergtwo(res,lists[i]);
        }
        return res;
    }
};

思路2:分治归并１

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwo(self, l1, l2):
        if l1 is None:
            return l2
        if l2 is None:
            return l1
        head = ListNode(0)
        node = head
        while l1 and l2:
            if l1.val <l2.val:
                node.next = l1
                l1 = l1.next
            else:
                node.next = l2
                l2 = l2.next
            node = node.next
        if l1:
            node.next = l1
        if l2:
            node.next = l2
        return head.next
    def mergeSort(self, lists, left, right):
        if left==right:
            return lists[left]
        middle = left + (right-left)//2
        # print('== middle:', middle)
        l1 = self.mergeSort(lists,left,middle)
        # print('== l1:', l1)
        l2 = self.mergeSort(lists,middle+1,right)
        return self.mergeTwo(l1, l2)


    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        # print('==hahah')
        if len(lists)==0:
            return None
        return self.mergeSort(lists,0,len(lists) - 1)

c++实现:?

/**
 * 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* mergetwo(ListNode* l1, ListNode* l2){
        if(l1==nullptr){
            return l2;
        }
        if(l2==nullptr){
            return l1;
        }
        ListNode* new_head= new ListNode(0);
        ListNode* node = new_head;
        while(l1 && l2){
            if(l1->val<l2->val){
                node->next = l1;
                l1= l1->next;
            }
            else{
                node->next = l2;
                l2= l2->next;
            }
            node = node->next;
        }
        if(l1){
            node->next = l1;
        }
        if(l2){
            node->next = l2;
        }
        return new_head->next;
    }
    ListNode* mergesort(vector<ListNode*>& lists,int left, int right){
        if(left==right){
            return lists[left];
            }
        int middle = left+(right -left)/2;
        ListNode* l1 = mergesort(lists,left,middle);
        ListNode* l2 = mergesort(lists,middle+1,right);
        return mergetwo(l1,l2);
        
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // ListNode* res = nullptr;
        // for (int i=0;i<lists.size();i++){
        //     res = mergtwo(res,lists[i]);
        // }
        // return res;
        if (lists.size()==0){
            return nullptr;
        }
        return mergesort(lists,0,lists.size()-1);
    }
};

思路3:分支归并２　参考排序算法的归并排序　https://blog.csdn.net/fanzonghao/article/details/81270601


class Solution:
    def mergeTwo(self, l1, l2):
        if l1 is None:
            return l2
        if l2 is None:
            return l1
        head = ListNode(0)
        node = head
        while l1 and l2:
            if l1.val < l2.val:
                node.next = l1
                l1 = l1.next
            else:
                node.next = l2
                l2 = l2.next
            node = node.next
        if l1:
            node.next = l1
        if l2:
            node.next = l2
        return head.next
    def mergeSort(self, L):
        if len(L) <= 1:
            return L[0]
        mid = len(L) // 2 
        l1 = self.mergeSort(L[:mid])
        l2 = self.mergeSort(L[mid:])
        return self.mergeTwo(l1, l2)
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if len(lists)==0:
            return None
        return self.mergeSort(lists)

3-3.合并两个有序链表

思路:递归终止条件就是节点为None.

１．递归法?

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        #递归的终止条件
        if l1 is None:
            return l2
        elif l2 is None:
            return l1    

        elif l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next,l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1,l2.next)
            return l2

２．迭代法：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        fake_head_node  = ListNode(0)

        cur = fake_head_node

        while l1 and l2:
            if l1.val<l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next            
            cur = cur.next
        
        if l1:
            cur.next = l1
        else:
            cur.next = l2

        return fake_head_node.next

3-4.排序链表

思路1:归并排序　先通过快慢指针找到中心点　进行截断以后一直递归拆开　在进行合并即可

python代码:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def merge(self, left, right):
        res = ListNode(0)
        temp = res
        while left and right:
            if left.val < right.val:
                temp.next, left = left, left.next
            else:
                temp.next, right = right, right.next
            temp = temp.next
        temp.next = left if left else right
        return res.next

    def sortList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head 
        #快慢指针找到链表中心点
        slow, fast = head, head.next
        while fast and fast.next:
            fast, slow = fast.next.next, slow.next
        mid, slow.next = slow.next, None#将找到的中心点进行截断故　slow.next = None
        
        left, right = self.sortList(head), self.sortList(mid)#递归一直进行拆分

        return self.merge(left, right)#合并操作

c++代码:

上一篇：让代码改变世界：《妙趣横生的算法》学习笔记说明

下一篇：没有了

立即下载 - IIS7 站长工具包