欢迎来到我的个人网站。交流请加我好友: 919201148。欢迎关注公众号或视频号:蜗牛互联网
Solo  当前访客:0 开始使用

白色蜗牛的互联网心得

我要一步一步往上爬,在最高点乘着叶片往前飞

标签: 链表 (5)

剑指Offer之二十六--复杂链表的复制

2016-04-07 22:21:14 huayonglun
0  评论    208  浏览

题目描述 输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点)。 复制一个复杂链表 结点定义 class RandomListNode { int label; RandomListNode next = null; RandomListNode random = null; public RandomListNode(int label){ this.label = label; } } 解析 遍历链表,每个结点后边复制相同的结点,设置next指针 复制结点的特殊指针。如果原始链表上的结点N的random指向S,则它对应的复制结点N的random指向S的下一个结点S 抽取复制结点,连起来得到复制链表 代码实现 public RandomListNode clone(RandomListNode pHead){ cloneNodes(pHead); connectRandomNodes(pHead); return reconnectNodes(pHead); } //复制原始链表的任意结点N并创建新结点N,再把N链....

, ,

剑指Offer之十五--链表中倒数第k个结点

2016-03-27 00:18:30 huayonglun
0  评论    224  浏览

链表结点结构 class ListNode{ int value; ListNode next = null; public ListNode(int value){ this.value = value; } } 基本解法 遍历两次,第一次确定链表长度,第二次返回第n-k+1个结点,即为所求 注意k不能超过链表长度,代码中要进行判断 public static ListNode findKthToTail(ListNode head,int k){ if(head == null || k <= 0 ){ return null; } ListNode node = head; int nodesNum = 1; while(node.next != null){ nodesNum++; node = node.next; } node = head; int count = 1; while(k <= nodesNum && count != nodesNum - k + 1){ count++; node = node.next; } if(k....

, ,

剑指Offer之十六--链表反转

2016-03-27 00:18:30 huayonglun
0  评论    215  浏览

链表结点结构 class ListNode{ int value; ListNode next = null; public ListNode(int value){ this.value = value; } } 题目描述 输入一个链表的头结点,反转该链表并输出翻转后的头结点 代码实现 遍历该链表 保存后一个结点,以防止当前结点的next值更新后链表断开 保存前一个结点,以便当前结点的next值更新为前一个结点 最后一个结点将是反转之后的头结点,保存该结点返回 public static ListNode reverseList(ListNode head) { ListNode reverseListHead = null; ListNode curNode = head; ListNode preNode = null; ListNode nextNode = null; while(curNode != null){ nextNode = curNode.next; if(nextNode == null){ reverseListHead = curNode; }....

, ,

剑指Offer之十七--合并两个排序的链表

2016-03-27 00:18:30 huayonglun
0  评论    217  浏览

链表结点结构 class ListNode{ int value; ListNode next = null; public ListNode(int value){ this.value = value; } } 题目描述 输入两个单调递增的链表,输出两个链表合成后的链表 当然我们需要合成后的链表满足单调不减规则 递归解法 比较两个链表的开头结点,则可以确定合并后链表的第一个结点 除合并后的结点外,再次比较两个链表的开头结点,则可以确定合并后链表的第二个结点 以此类推,直到所有结点均成为合并后链表中的结点 public static ListNode merge(ListNode list1,ListNode list2) { if(list1 == null){ return list2; } if(list2 == null){ return list1; } ListNode mergeListHead = null; if(list1.value < list2.value){ mergeListHead = list1; mergeListHead.nex....

, , ,

每K个结点反转单链表

2016-04-06 23:42:47 huayonglun
0  评论    213  浏览

题目描述 给定一个常数K以及一个单链表L,请编写程序将L中每K个结点反转。 例如:给定L为1→2→3→4→5→6,K为3,则输出应该为3→2→1→6→5→4; 如果K为4,则输出应该为4→3→2→1→5→6,即最后不到K个元素不反转。 思路 通过链表长度和K值确定需要反转的结点数 每K个反转成新链表,把头保存到List中 需要反转的结点数已到并且剩下的结点数不足K个,不反转,即把当前结点存到List中 把List中各个链表连接 代码 package com.liuyong666.pat; import java.util.ArrayList; import java.util.List; public class Main { static class ListNode{ int val; ListNode next = null; public ListNode(int val){ this.val = val; } } public static ListNode reversePartNode(ListNode head, int k){ if(head == null ....

, ,
TOP