关于java:2021字节跳动秋招校招算法面试热门真题精讲-内含7种语言答案

36次阅读

共计 5348 个字符,预计需要花费 14 分钟才能阅读完成。

排序链表

1. 题目形容

<p> 在 O(n log n) 工夫复杂度和常数级空间复杂度下,对链表进行排序。</p><br/><p> 示例 1:</p><br/><pre> 输出: 4->2->1->3<br/> 输入: 1->2->3->4<br/></pre><br/><p> 示例 2:</p><br/><pre> 输出: -1->5->3->4->0<br/> 输入: -1->0->3->4->5</pre><br/>

c 答案


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

//head 不参加排序!void mergeSortList(struct ListNode* head) {
    struct ListNode* slow, *fast,*pre;
    if (NULL == head)
        return;    // 有效输出
    else{
        struct ListNode R;
        slow = fast = head;
        do {if ((fast = fast->next) != NULL) {
                fast = fast->next;
                slow = slow->next;
            }
        } while (fast);
        if (NULL == slow->next)return;    // 只有 0 或 1 个元素
        R.next = slow->next;
        slow->next = NULL;    // 一分为二
        mergeSortList(head);    // 使左半有序
        mergeSortList(&R);        // 使右半有序
        slow = head->next;    fast = R.next;    // 两边筹备进行归并
    }
    pre = head;    // 尾插法(是 slow 的前驱)do {if (fast->val < slow->val) {    // 左边比右边小
            pre = pre->next = fast;        // 原 pre->next==slow,所以不会丢链
            fast = fast->next;
            pre->next = slow;            // 还原 pre 是 slow 的前驱
            if (fast == NULL) 
                break;        // 右边的 pre 原本就接着 slow,无需解决
        }
        else {    // 右边小
            pre = slow;
            slow = slow->next;
            if (slow == NULL) {
                pre->next = fast;        // 残余的左边接到右边
                break;
            }
        }
    } while (true);
}

struct ListNode* sortList(struct ListNode* head) {
    struct ListNode Head; Head.next = head;    // 真正头结点,不参加排序
    mergeSortList(&Head);
    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 * merge(ListNode* left, ListNode* right)
    {
        ListNode* newhead = NULL, *pre=NULL;
        while (left && right)
        {if (left->val < right->val)
            {if (!newhead)
                {
                    newhead = pre = left;
                    left = left->next;
                }
                else
                {
                    pre->next = left;
                    pre = pre->next;
                    left = left->next;
                }
            }
            else
            {if (!newhead)
                {
                    newhead = pre = right;
                    right = right->next;
                }
                else
                {
                    pre->next = right;
                    pre = pre->next;
                    right = right->next;
                }
            }
        }
        while (left)
        {
            pre->next = left;
            left = left->next;
            pre = pre->next;
        }
        while (right)
        {
            pre->next = right;
            right = right->next;
            pre = pre->next;
        }
        pre->next = NULL;
        return newhead;
    }

    ListNode* sortList(ListNode* head) {if (head == NULL || head->next == NULL)
            return head;
        else
        {
            ListNode* slow = head, *fast = head->next;
            while (fast != NULL && fast->next != NULL)
            {
                slow = slow->next;
                fast = fast->next->next;
            }
            ListNode* temp = slow->next;
            slow->next = NULL;
            ListNode* l = sortList(head);
            ListNode* r = sortList(temp);
            return merge(l, r);
        }
    }
};

java 答案


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {val = x;}
 * }
 */
class Solution {public ListNode sortList(ListNode head) {if (head == null || head.next == null) return head;
        ListNode fast = head;
        ListNode slow = head;
        // 快慢指针寻找链表的两头节点
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 把链表分为两段
        ListNode l1 = head;
        ListNode l2 = slow.next;
        slow.next = null;

        // Merge Sort
        l1 = sortList(l1);
        l2 = sortList(l2);
        return merge(l1, l2);
    }

    // 归并两个曾经排好序的链表
    private ListNode merge(ListNode l1, ListNode l2) {if (l1 == null) return l2;
        if (l2 == null) return l1;

        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (l1 != null && l2 != null) {if (l1.val <= l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }

        if (l1 != null) cur.next = l1;
        else cur.next = l2;
        return dummy.next;
    }
}

JavaScript 答案


/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var merge = function(l1,l2) {var l = new ListNode();
    var p = l;
    while(l1 && l2) {if(l1.val < l2.val) {
            p.next = l1;
            l1 = l1.next
        } else {
            p.next = l2;
            l2 = l2.next
        }
        p = p.next
    }
    if(l1) {p.next = l1;}
    if(l2) {p.next = l2;}
    return l.next;
}
var sortList = function(head) {if(head === null || head.next === null) {return head;}
    var slow = head;
    var fast = head;
    var prev = null;
    while(fast && fast.next) {
        prev = slow
        fast = fast.next.next;
        slow = slow.next
    }
    prev.next = null;
    return merge(sortList(head), sortList(slow));
};

c# 答案


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) {val = x;}
 * }
 */
public class Solution {public ListNode SortList(ListNode head) {if(head == null) return head;    
        ListNode now = head;
            List<int> list = new List<int>();
            while(now != null)
            {list.Add(now.val);
                now = now.next;
            }
            list.Sort();
            int length = list.Count;
            ListNode result = new ListNode(list[0]);
            now = result;
            for(int i=1;i<length;i++)
            {now.next = new ListNode(list[i]);
                now = now.next;
            }
            return result;
    }
}

python2.x 答案


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

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        node = head
        res=[]
        while node:
            res.append(node.val)
            node = node.next
        res.sort()
        if not res:
            return None
        newhead = ListNode(res[0])
        cur_Node = newhead
        for i,v in enumerate(res):
            if i == 0:
                continue
            obj = ListNode(v)
            cur_Node.next=obj
            cur_Node=obj
        return newhead


                
            
        

python3.x 答案


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

class Solution:
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head: return None 
        res = []
        while head:
            res.append(head)
            head = head.next
        res.sort(key = lambda ele: ele.val)
        temp = res[0]
        for i in range(1,len(res)):
            temp.next = res[i]
            temp = res[i]
        res[-1].next = None 
        return res[0]
        

go 答案


/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func sortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {return head}
    
    middle := split(head)
    
    return merge(sortList(head), sortList(middle))
}

// 双指针切分 list
func split(head *ListNode) *ListNode {
    slow, fast := head, head
    var tail *ListNode
    
    for fast != nil && fast.Next != nil {
        tail = slow
        slow = slow.Next
        fast = fast.Next.Next
    }
    
    tail.Next = nil
    return slow
}

func merge(left ,right *ListNode) *ListNode {
    var head, cur, pre *ListNode
    for left != nil && right != nil {
        if left.Val < right.Val {
            cur = left
            left = left.Next
        } else {
            cur = right
            right = right.Next
        }
        // 生成 head
        if head == nil {head = cur} else {pre.Next = cur}
        pre = cur
    }
    
    if left == nil {pre.Next = right} else {pre.Next = left}
    
    return head
}

更多算法题目精解 请微信扫一扫小程序“算法面试宝典”,实现算法面试自在的神器

正文完
 0