freeCodeCamp/curriculum/challenges/japanese/10-coding-interview-prep/data-structures/reverse-a-doubly-linked-list.md

id, title, challengeType, forumTopicId, dashedName

id	title	challengeType	forumTopicId	dashedName
587d825a367417b2b2512c88	二重リンクリストを逆順にする	1	301714	reverse-a-doubly-linked-list

--description--

二重リンクリストに対して、通りがけ順にリストを逆にする reverse というメソッドを作りましょう。 このメソッドが実行されると、ヘッドは以前のテールを指し、テールは以前のヘッドを指します。 こうすると、ヘッドからテールまでリストを走査したときに、元のリストとは逆の順序でノードを訪問することになります。 空のリストを逆順にしようとすると、null が返される必要があります。

--hints--

DoublyLinkedList データ構造が存在する必要があります。

assert(
  (function () {
    var test = false;
    if (typeof DoublyLinkedList !== 'undefined') {
      test = new DoublyLinkedList();
    }
    return typeof test == 'object';
  })()
);

DoublyLinkedList に reverse というメソッドが必要です。

assert(
  (function () {
    var test = false;
    if (typeof DoublyLinkedList !== 'undefined') {
      test = new DoublyLinkedList();
    }
    if (test.reverse == undefined) {
      return false;
    }
    return typeof test.reverse == 'function';
  })()
);

空のリストを逆順にすると、null が返される必要があります。

assert(
  (function () {
    var test = false;
    if (typeof DoublyLinkedList !== 'undefined') {
      test = new DoublyLinkedList();
    }
    return test.reverse() == null;
  })()
);

reverse メソッドはリストを逆順にする必要があります。

assert(
  (function () {
    var test = false;
    if (typeof DoublyLinkedList !== 'undefined') {
      test = new DoublyLinkedList();
    }
    test.add(58);
    test.add(61);
    test.add(32);
    test.add(95);
    test.add(41);
    test.reverse();
    return test.print().join('') == '4195326158';
  })()
);

リストが逆順になったとき、次の参照と前の参照が正しく維持される必要があります。

assert(
  (function () {
    var test = false;
    if (typeof DoublyLinkedList !== 'undefined') {
      test = new DoublyLinkedList();
    }
    test.add(11);
    test.add(22);
    test.add(33);
    test.add(44);
    test.add(55);
    test.reverse();
    return test.printReverse().join('') == '1122334455';
  })()
);

--seed--

--after-user-code--

DoublyLinkedList.prototype = Object.assign(
  DoublyLinkedList.prototype,
  {
    add(data) {
      if (this.head == null) {
        this.head = new Node(data, null);
        this.tail = this.head;
      } else {
        var node = this.head;
        var prev = null;
        while (node.next != null) {
          prev = node;
          node = node.next;
        };
        var newNode = new Node(data, node);
        node.next = newNode;
        this.tail = newNode;
      };
    },
    print() {
      if (this.head == null) {
        return null;
      } else {
        var result = new Array();
        var node = this.head;
        while (node.next != null) {
          result.push(node.data);
          node = node.next;
        };
        result.push(node.data);
        return result;
      };
    },
    printReverse() {
      if (this.tail == null) {
        return null;
      } else {
        var result = new Array();
        var node = this.tail;
        while (node.prev != null) {
          result.push(node.data);
          node = node.prev;
        };
        result.push(node.data);
        return result;
      };
    }
  }
);

--seed-contents--

var Node = function(data, prev) {
  this.data = data;
  this.prev = prev;
  this.next = null;
};
var DoublyLinkedList = function() {
  this.head = null;
  this.tail = null;
  // Only change code below this line

  // Only change code above this line
};

--solutions--

  var Node = function(data, prev) {
    this.data = data;
    this.prev = prev;
    this.next = null;
  };
  var DoublyLinkedList = function() {
    this.head = null;
    this.tail = null;

    this.reverse = function() {
      if (!this.head || !this.head.next) {
        return this.head
      }

      let tail;
      let temp;
      let current = this.head;
      while(current !== null) {
        if(!tail) tail = current;
        temp = current.prev;
        current.prev = current.next;
        current.next = temp;
        current = current.prev;
      }

      this.head = temp.prev;
      this.tail = tail
    }
  };