tôi nghe một câu hỏi phỏng vấn: "In một danh sách đơn lẻ liên kết ngược, trong không gian liên tục và thời gian tuyến tính"In một danh sách đơn lẻ liên kết ngược, trong không gian liên tục và thời gian tuyến tính
Giải pháp của tôi là đảo ngược danh sách được liên kết tại chỗ rồi in như thế. Có một giải pháp không phá hủy không?
Nếu bạn đảo ngược nó một lần nữa sau khi in nó sẽ không còn là phá hoại, vì trật tự ban đầu được phục hồi.
Bạn có thể sử dụng cuộc gọi đệ quy xuống chuỗi danh sách được liên kết với tham chiếu đến nội dung bạn muốn ghi. Mỗi nút sẽ sử dụng chức năng in của nút con trong khi truyền tham chiếu trước khi in chính nó.
Bằng cách đó, mỗi nút trong danh sách sẽ chuyển xuống, cho đến khi nút cuối cùng không thể và sẽ đi thẳng đến ghi, sau đó mỗi nút sao lưu chuỗi sẽ ghi sau lần cuối cùng quay trở lại phía trước .
Sửa
Điều này thực sự không phù hợp với thông số kỹ thuật vì không gian tuyến tính trên stack. Nếu bạn có một cái gì đó bên ngoài để đi bộ các chức năng và một phương pháp viết vào mặt trước của một chuỗi logic cơ sở vẫn có thể làm việc mặc dù.
Nhưng điều đó sẽ sử dụng không gian ngăn xếp O (n) =/ –
Không gian tuyến tính - ngăn xếp được tính là không gian. –
@Razor - lol, bạn chỉ cần nhanh hơn một chút trên bàn phím. –
Chỉ cần lặp lại và in dọc theo đường nhưng xoay màn hình của bạn lộn ngược.
˙uoıʇɐɯɹoɟsuɐɹʇ ʇxǝʇ ǝlʇʇıl ɐ ɥʇıʍ ʇɥƃıɹ ʇsoɯlɐ ʞool uɐɔ ʇI
LOL giải pháp tốt nhất cho đến nay –
Aw man, anh ta đánh tôi với nó. –
Dưới đây là một cách tiếp cận độc đáo: Thay đổi bảng điều khiển của bạn thành thứ tự đọc từ phải sang trái rồi in danh sách theo thứ tự bình thường. Chúng sẽ xuất hiện theo thứ tự lạc hậu. Việc phải truy cập dữ liệu thực tế theo thứ tự ngược lại không có vẻ giống như một ràng buộc đối với vấn đề.
Bạn đã tìm ra hầu hết câu trả lời: đảo ngược danh sách được liên kết tại chỗ và duyệt qua danh sách quay lại đầu để in nó. Để giữ cho nó khỏi bị (vĩnh viễn) phá hoại, đảo ngược danh sách liên kết tại chỗ một lần nữa khi bạn đang di chuyển nó trở lại đầu và in nó. Tuy nhiên, hãy lưu ý rằng điều này chỉ hoạt động nếu bạn chỉ có một chuỗi thực thi duy nhất hoặc chuyển toàn bộ một phần quan trọng để chỉ có một luồng tại một thời điểm (ví dụ: chuỗi thứ hai không bao giờ có thể chơi được danh sách ở giữa traversal).
Cả hai câu trả lời hàng đầu đều trả lời chính xác câu hỏi này. Tôi đã chọn cái khác vì nó đã được đăng trước đó. Nhưng tôi đã bỏ phiếu này vì nó có nhiều chi tiết hơn. Quá tệ SO không cho phép tôi chấp nhận nhiều câu trả lời nếu chúng rất giống nhau: [ –
Được rồi, đây có thể là câu hỏi phỏng vấn, nhưng đó thực sự là câu hỏi đằng sau sách thuật toán của weis. Câu hỏi nêu rõ rằng chúng ta không thể sử dụng đệ quy (một điều mà người phỏng vấn sẽ giấu và tiết lộ sau này) khi đệ quy sẽ không sử dụng không gian liên tục, đệ quy moslty sẽ trở thành một điểm chính của sự phân tích về sau. Giải pháp là in ngược và ngược lại.
Đó là những gì tôi đã suy nghĩ. Tuy nhiên, đó là thực hành tốt trong một tình huống thế giới thực?(Giả sử vượt qua tham chiếu) –
Thực ra bạn sẽ đảo ngược nó đầu tiên mà không cần in và sau đó in nó trong khi bạn đảo ngược lại. – x4u
@Razor: ish. Thông thường nếu bạn vượt qua một cái gì đó để in, bạn sẽ mong đợi các callee để xử lý nó như là unmodifiable. Vì vậy, trong các ngôn ngữ quan tâm đến loại điều đó, hoặc chức năng cần (đáng ngạc nhiên) lấy một tham số không phải là const hoặc khác chính hàm đó phải chứa mã không an toàn. Bạn sẽ phải quyết định xem các lợi ích có đáng để thêm nguy cơ viết mã không đúng hay không hoặc bạn có nên thực hiện tốt hơn việc sao chép danh sách hay sử dụng cấu trúc hai chiều thay thế (ví dụ: danh sách được liên kết kép). Nếu đó là một lợi ích đủ nghiêm trọng, thực hành tốt của bất cứ điều gì ;-) –