基础算法题-链表相关
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;
}
上一篇: 是生活触动了Ta们的幽默神经
下一篇: 生物识别:单对象人脸识别技术研究