lazyken

# 金典问题

# 反转链表

反转一个单链表。

示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

// 方法一：迭代
var reverseList = function(head) {
  var prev = null;
  var curr = head;
  // 遍历链表,将链表的指针依次反转
  while (curr) {
    var temp = curr;
    curr = curr.next;
    temp.next = prev;
    prev = temp;
  }
  return prev;
};

// 方法二：递归
var reverseList = function(head) {
  if (!head) {
    return null;
  }
  var tail = head;
  function goNext(node) {
    if (node.next) {
      var temp = goNext(node.next);
      temp.next = node;
    } else {
      tail = node;
    }
    node.next = null;
    return node;
  }
  goNext(head);
  return tail;
};

# 移除链表元素

删除链表中等于给定值 val 的所有节点。

示例:
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

var removeElements = function(head, val) {
  var sentinel = { next: head };
  var curr = head;
  var prev = sentinel;
  while (curr) {
    if (curr.val === val) {
      prev.next = curr.next;
    } else {
      prev = curr;
    }
    curr = curr.next;
  }
  return sentinel.next;
};

# 奇偶链表

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例 1:
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL

示例 2:
输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL

说明:
应当保持奇数节点和偶数节点的相对顺序。
链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

// 方法一：拼接法，将奇数项和偶数项分开拼接，最后再将奇数链和偶数链链接
var oddEvenList = function(head) {
  if (!head) {
    return head;
  }
  var index = 1;
  var odd = null;
  var event = null;
  var curr = head;
  var eventHead = null;
  while (curr) {
    var temp = curr;
    curr = curr.next;
    temp.next = null;
    if (index % 2 !== 0) {
      // 奇数
      if (odd) {
        odd.next = temp;
      }
      odd = temp;
    } else {
      // 偶数
      if (event) {
        event.next = temp;
      } else {
        eventHead = temp;
      }
      event = temp;
    }
    index++;
  }
  odd.next = eventHead;
  return head;
};

# 回文链表

请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

// 方法一：将数值复制到数组后用双指针法
var isPalindrome = function(head) {
  var valList = [];
  var curr = head;
  while (curr) {
    valList.push(curr.val);
    curr = curr.next;
  }
  var res = true;
  for (var i = 0, j = valList.length - 1; i < j; i++, j--) {
    if (valList[i] !== valList[j]) {
      res = false;
      break;
    }
  }
  return res;
};

// 方法二：递归判断
var isPalindrome = function(head) {
  var frontHead = head;
  function goNext(node) {
    // 尾结点直接返回true
    if (node) {
      // 递归，如果递归的下一层返回false，即不是回文，本层也直接返回false
      if (!goNext(node.next)) {
        return false;
      }
      // 判断是否为回文
      if (node.val !== frontHead.val) {
        // 不是回文则返回false
        return false;
      }
      // frontHead指针从头开始遍历
      frontHead = frontHead.next;
    }
    // 尾结点直接返回true
    return true;
  }
  return goNext(head);
};

// 方法三：快慢指针
// 步骤：
// 1、利用快慢指针找到链表中点节点
// 2、反转后半段链表
// 3、遍历对比前后两段链表
// 4、还原链表
var isPalindrome = function(head) {
  if (!head || !head.next) {
    return true;
  }
  var slow = { next: head };
  var fast = { next: head };
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  // 前半段长度>=后半段
  var mind = slow.next;
  // 切断前后两段
  slow.next = null;
  // 新指针分别记录前后2段链表
  var link1 = head;
  var link2 = mind;
  function reverseLink(link) {
    var prev = null;
    var curr = link;
    while (curr) {
      var temp = curr;
      curr = curr.next;
      temp.next = prev;
      prev = temp;
    }
    return prev;
  }
  link2 = reverseLink(link2);
  var saveLink2 = link2;
  var res = true;
  while (link2) {
    if (link1.val === link2.val) {
      link1 = link1.next;
      link2 = link2.next;
    } else {
      break;
    }
  }
  if (link2) {
    res = false;
  }
  mind.next = reverseLink(saveLink2);
  return res;
};

← 双链表 →