访问单个节点的删除、链表的分化、打印两个链表的公共值

落日映苍穹つ 2022-06-09 02:44 108阅读 0赞

*   *   *  访问单个节点的删除
         *  链表的分化
         *  打印两个链表的公共值

--------------------

### 访问单个节点的删除 ###

实现一个算法，删除单向链表中间的某个结点，假定你只能访问该结点。

给定带删除的头节点和要删除的数字，请执行删除操作，返回删除后的头结点。链表中没有重复数字

**我的提交**  
（是我理解错题意了？？？）

# -*- coding:utf-8 -*-
    # class ListNode:
    # def __init__(self, x):
    # self.val = x
    # self.next = None
    
    class Remove:
        def removeNode(self, pHead, delVal):
            # write code here
            if pHead.val == delVal:
                pHead = pHead.next
                return pHead
            p1 = pHead
            p2 = None
            while p1.next != None:
                p2 = p1
                p1 = p1.next
                if p1.val == delVal:
                    p2.next = p1.next
                    break
            return pHead

**参考答案**

import java.util.*;
    
    /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/
    public class Remove { 
        public boolean removeNode(ListNode pNode) {
            if (pNode == null) {
                return false;
            }
            ListNode next = pNode.next;
            if (next == null) {
                return false;
            }
            pNode.val = next.val;
            pNode.next = next.next;
            return true;
        }
    }

--------------------

### 链表的分化 ###

对于一个链表，我们需要用一个特定阈值完成对它的分化，**使得小于等于这个值的结点移到前面，大于该值的结点在后面，同时保证两类结点内部的位置关系不变**。

给定一个链表的头结点head，同时给定阈值val，请返回一个链表，使小于等于它的结点在前，大于等于它的在后，保证结点值不重复。

测试样例：
    {
       1,4,2,5},3
    {
       1,2,4,5}

**我的提交**  
（审错题了）

# -*- coding:utf-8 -*-
    # class ListNode:
    # def __init__(self, x):
    # self.val = x
    # self.next = None
    
    class Divide:
        def __init__(self):
            self.pointer = [[], [], []]
    
        def listDivide(self, head, val):
            # write code here
            for item in head:
                if item < val:
                    self.pointer[0].append(item)
                elif item == val:
                    self.pointer[1].append(item)
                else:
                    self.pointer[2].append(item)
            return self.pointer[0] + self.pointer[1] + self.pointer[2]
    
    if __name__ == '__main__':
        d = Divide()
        result = d.listDivide({
       1,4,2,5},3)
        print(result)

**参考答案**

import java.util.*;
    
    /*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class Divide {
        public ListNode listDivide(ListNode head, int pivot) {
            ListNode sH = null; // small head
            ListNode sT = null; // small tail
            ListNode bH = null; // big head
            ListNode bT = null; // big tail
            ListNode next = null; // save next node
            // every node distributed to three lists
            while (head != null) {
                next = head.next;
                head.next = null;
                if (head.val <= pivot) {
                    if (sH == null) {
                        sH = head;
                        sT = head;
                    } else {
                        sT.next = head;
                        sT = head;
                    }
                }else {
                    if (bH == null) {
                        bH = head;
                        bT = head;
                    } else {
                        bT.next = head;
                        bT = head;
                    }
                }
                head = next;
            }
            if (sT != null) {
                sT.next = bH;
            }
            return sH != null ? sH : bH;
        }
    }

--------------------

### 打印两个链表的公共值 ###

现有两个升序链表，且链表中均无重复元素。请设计一个高效的算法，打印两个链表的公共值部分。

给定两个链表的头指针headA和headB，请返回一个vector，元素为两个链表的公共部分。请保证返回数组的升序。两个链表的元素个数均小于等于500。保证一定有公共值

# 测试样例：
    {
       1,2,3,4,5,6,7},{
       2,4,6,8,10}
    返回：[2.4.6]

**我的提交**

# -*- coding:utf-8 -*-
    # class ListNode:
    # def __init__(self, x):
    # self.val = x
    # self.next = None
    
    class Common:
        def findCommonParts(self, headA, headB):
            # write code here
            if not headA or not headB:
                return []
            result = []
            while headA and headB:
                if headA.val == headB.val:
                    result.append(headA.val)
                    headA = headA.next
                    headB = headB.next
                elif headA.val < headB.val:
                    headA = headA.next
                else:
                    headB = headB.next
            return result

**参考答案**

import java.util.*;
    
    /*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class Common {
        public int[] findCommonParts(ListNode head1, ListNode head2) {
            LinkedList list = new LinkedList();
            while (head1 != null && head2 != null) {
                if (head1.val < head2.val) {
                    head1 = head1.next;
                } else if (head1.val > head2.val) {
                    head2 = head2.next;
                } else {
                    list.add(head1.val);
                    head1 = head1.next;
                    head2 = head2.next;
                }
            }
            int[] res = new int[list.size()];
            int index = 0;
            while (!list.isEmpty()) {
                res[index++] = list.pollFirst();
            }
            return res;
        }
    }