Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

k个一组翻转链表 #48

Open
louzhedong opened this issue Sep 5, 2018 · 0 comments
Open

k个一组翻转链表 #48

louzhedong opened this issue Sep 5, 2018 · 0 comments

Comments

@louzhedong
Copy link
Owner

习题

出处:LeetCode 算法第25题

给出一个链表,每 k 个节点一组进行翻转,并返回翻转后的链表。

k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么将最后剩余节点保持原有顺序。

示例 :

给定这个链表:1->2->3->4->5

k = 2 时,应当返回: 2->1->4->3->5

k = 3 时,应当返回: 3->2->1->4->5

说明 :

  • 你的算法只能使用常数的额外空间。
  • 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

思路

先统计有几个k个元素,对每k个元素进行链表的翻转,再组成长链表

解答

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
function ListNode(val) {
  this.val = val;
  this.next = null;
}
var reverseKItem = function (head, k) {
  var start = head;
  var tail = head;
  var current = 0;

  var prev = next = null;
  while (head && current < k) {
    next = head.next;
    head.next = prev;
    prev = head;
    start = head;
    current++;
    head = next;
  }
  tail.next = next;
  return [start, tail];
}
var reverseKGroup = function (head, k) {
  if (!head || !head.next || k <= 1) {
    return head;
  }
  // 计算链表的长度
  var length = 0;
  var tempNode = head;
  while (tempNode) {
    length++;
    tempNode = tempNode.next;
  }
  var empty = new ListNode();
  var prev = empty;

  var i = 0;
  while (head && head.next) {
    if (k > (length - i)) break;
    var [rHead, rTail] = reverseKItem(head, k);
    prev.next = rHead;
    prev = rTail;
    head = rTail.next;
    i += k;
  }
  return empty.next || head;
};

var head = new ListNode(1);
var aaa = head;
head.next = new ListNode(2);
head = head.next;
head.next = new ListNode(3);
head = head.next;
head.next = new ListNode(4);
head = head.next;
head.next = new ListNode(5);

console.log(reverseKGroup(aaa, 3));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant