基础算法题-链表相关

1. 输入一个链表，从尾到头打印链表每个节点的值。

先递归，再添加节点的值即可。 代码如下：

ArrayList<Integer> printListFromTailToHead(ListNode listNode) { ArrayList<Integer> array = new ArrayList<Integer>(); if (listNode != null) { array = printListFromTailToHead(listNode.next); array.add(listNode.val); } return array; }

2. 输入一个链表，输出该链表中倒数第k个结点。

设置两个指针指向链表头，一个先走K步，然后两个指针一起向后移动，第一个指针到尾部时候，第二个指针即倒数第K个结点。 代码如下：

ListNode FindKthToTail(ListNode head, int k) { if (head == null | k < 0) return null; ListNode pointer1 = head; ListNode pointer2 = head; int count = 1; while (pointer2.next != null) { if (count < k) { pointer2 = pointer2.next; count++; } else { pointer2 = pointer2.next; pointer1 = pointer1.next; } } if (count == k) return pointer1; else return null; }

3. 输入一个链表，反转链表后，输出链表的所有元素。

用两种方式来解决，第一种递归解决，考虑有一个k结点，将k结点后链表逆转后的头结点返回，此时k结点指向的结点是逆转后链表的尾部结点，将k结点移到逆转后链表的尾部即可。 代码如下：

ListNode ReverseList(ListNode head) { if (head == null) return null; //递归解决 if (head.next == null) return head; ListNode head1 = ReverseList(head.next); head.next.next = head; head.next = null; return head1; }

第二种方式，通过在原始链表中操作，采用头插法即可逆置。 代码如下：

ListNode ReverseList(ListNode head) { if (head == null) return null; ListNode pointer = head.next; ListNode pointer1 = head; while (pointer != null) { head.next = pointer.next; pointer.next = pointer1; pointer1 = pointer; pointer = head.next; } return pointer1; }

4. 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

两种方式解决，一种递归，首先比较两个链表的头结点，获得了一个较小的结点，此时应该递归比较结点后的链表和另一个链表即可。 代码如下：

ListNode Merge(ListNode list1, ListNode list2) { if (list1 == null) return list2; if (list2 == null) return list1; ListNode pointer1 = list1; ListNode pointer2 = list2; //递归实现 if (list1.val <= list2.val) { pointer1 = list1; pointer1.next = Merge(list1.next, list2); } else { pointer1 = list2; pointer1.next = Merge(list1, list2.next); } return pointer1; }

第二种迭代解决。采用尾插法，不断的将较小的结点插入。代码如下：

ListNode Merge(ListNode list1, ListNode list2) { if (list1 == null) return list2; if (list2 == null) return list1; ListNode pointer1 = list1; ListNode pointer2 = list2; ListNode head = new ListNode(0); ListNode rear = head;//尾插法 while (pointer1 != null && pointer2 != null) { if (pointer1.val <= pointer2.val) { rear.next = pointer1; rear = pointer1; pointer1 = pointer1.next; } else if (pointer1.val > pointer2.val) { rear.next = pointer2; rear = pointer2; pointer2 = pointer2.next; } } if (pointer1 != null) rear.next = pointer1; else if (pointer2 != null) rear.next = pointer2; return head.next; }

5. 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。

首先在原始复杂链表上进行复制结点操作，例如1->2->3变为1->1->2->2->3->3。然后将特殊的指针也进行赋值。每个特殊指针不为空的结点后一个结点的特殊指针指向，前一个结点特殊指针指向的结点的下一个。最后将结点分离出来即可。 代码如下：

/* public class RandomListNode { int label; RandomListNode next = null; RandomListNode random = null; RandomListNode(int label) { this.label = label; } } */ RandomListNode Clone(RandomListNode pHead) { if (pHead == null) return null; RandomListNode pointer = pHead; while (pointer != null) { RandomListNode node = new RandomListNode(pointer.label); node.next = pointer.next; pointer.next = node; pointer = node.next; } pointer = pHead; while (pointer != null) { if (pointer.random == null) pointer.next.random = null; else { pointer.next.random = pointer.random.next; } pointer = pointer.next.next; } pointer = pHead; RandomListNode result = pHead.next; while (pointer != null) { RandomListNode node = pointer.next; pointer.next = pointer.next.next; pointer = pointer.next; if (pointer != null && pointer.next != null) { node.next = pointer.next; } } return result; }

6. 输入两个链表，找出它们的第一个公共结点。

有多种方式，这里介绍两种，可以用两个栈将两个链表结点保存，然后两个栈同时出栈进行对比即可，另一个先计算链表长度，然后进行比对。这里只给出第二种的代码，如下：

ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { int len1 = 0, len2 = 0; if (pHead1 == null | pHead2 == null) return null; ListNode pointer1 = pHead1, pointer2 = pHead2; while (pointer1 != null) { len1++; pointer1 = pointer1.next; } while (pointer2 != null) { len2++; pointer2 = pointer2.next; } pointer1 = pHead1; pointer2 = pHead2; int more = Math.abs(len1 - len2); if (len1 <= len2) { pointer2 = pHead1; pointer1 = pHead2; } while (pointer1 != null && pointer2 != null) { if (more > 0) { pointer1 = pointer1.next; more--; } else { if (pointer1 == pointer2) { return pointer1; } pointer1 = pointer1.next; pointer2 = pointer2.next; } } return pointer1; }

7. 一个链表中包含环，请找出该链表的环的入口结点。

设置三个指针，一个指针走两步，第二个指针走一步，第三个指针在表头。等两个指针在链表中相遇时候，第二个指针和第三个指针同时出发，按一步长走即可，相遇即为入口结点。 代码如下：

ListNode EntryNodeOfLoop(ListNode pHead) { if (pHead == null | pHead.next == null) return null; ListNode pointer1 = pHead, pointer2 = pHead; boolean flag = true; while (flag) { pointer1 = pointer1.next; pointer2 = pointer2.next.next; if (pointer1 == pointer2) { flag = false; } } pointer1 = pHead; if (pointer1 == pointer2) { flag = true; } while (!flag) { pointer1 = pointer1.next; pointer2 = pointer2.next; if (pointer1 == pointer2) { flag = true; } } return pointer2; }

8. 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5。

递归实现，当某结点没有重复，则此结点指向后续结点的处理返回的链表。若有重复，则将结点迭代至最后一个重复结点处，然后后续结点处理返回的链表头结点即头结点，也就是会略过这个结点。 代码如下：

ListNode deleteDuplication(ListNode pHead) { if (pHead == null || pHead.next == null) { return pHead; } ListNode head = pHead; boolean flag = false; int val = pHead.val; while (pHead.next != null && val == pHead.next.val) { pHead = pHead.next; flag = true; } if (!flag) { head.next = deleteDuplication(pHead.next); } else { head = deleteDuplication(pHead.next); } return head; }