[算法]在单链表和双链表中删除倒数第k个结点

题目：

分别实现两个函数，一个可以删除单链表中倒数第K个节点，另一个可以删除双链表中倒数第K个节点。

要求：

如果链表长度为N，时间复杂度达到O(N)，额外空间复杂度达到O(1)。

解答：

让链表从头走到尾，每移动一步，就让K值减一，当链表走到结尾时，如果K值大于0，说明不用调整链表，因为链表根本没有倒数第K个节点，此时将原链表直接返回即可；如果K值等于0，说明链表倒数第K个节点就是头结点，此时直接返回head.next，相当于删除了头结点。当K的值小于零时，再次从头结点开始走，每移动一步，就让K的值加1。当K等于0时，移动停止，移动的结到的结点就是要删除的结点的前一个结点。

链表长度为N,要删除倒数第K个节点，那么倒数第K个节点的前一个结点就是第N-K个节点。在第一次遍历之后，K的值变为了K-N。第二次遍历时，K的值不断加1.加到0就停止遍历，所在的位置就是第N-K个节点的位置。

程序：

单链表：

public static class Node {

		public int value;

		public Node next;


		public Node(int data) {

			this.value = data;

		}

	}


	public static Node removeLastKthNode(Node head, int lastKth) {

		if (head == null || lastKth < 1) {

			return head;

		}

		Node cur = head;

		while (cur != null) {

			lastKth--;

			cur = cur.next;

		}

		if (lastKth == 0) {

			head = head.next;

		}

		if (lastKth < 0) {

			cur = head;

			while (++lastKth != 0) {

				cur = cur.next;

			}

			cur.next = cur.next.next;

		}

		return head;

	}

双链表：

public static class DoubleNode {

		public int value;

		public DoubleNode last;

		public DoubleNode next;


		public DoubleNode(int data) {

			this.value = data;

		}

	}


	public static DoubleNode removeLastKthNode(DoubleNode head, int lastKth) {

		if (head == null || lastKth < 1) {

			return head;

		}

		DoubleNode cur = head;

		while (cur != null) {

			lastKth--;

			cur = cur.next;

		}

		if (lastKth == 0) {

			head = head.next;

			head.last = null;

		}

		if (lastKth < 0) {

			cur = head;

			while (++lastKth != 0) {

				cur = cur.next;

			}

			DoubleNode newNext = cur.next.next;

			cur.next = newNext;

			if (newNext != null) {

				newNext.last = cur;

			}

		}

		return head;

	}

巴特西

[算法]在单链表和双链表中删除倒数第k个结点

题目：

要求：

解答：

程序：

最新文章

热门文章