找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 625|回复: 7
收起左侧

[刷题总结] 关于list的一点心得

[复制链接]

11

主题

5

精华

156

积分

资深会员

Rank: 2

积分
156
发表于 12-1-2017 07:15 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
大家好, 我是彩笔色娃。
在各种数据结构中,个人认为最简单的就是【i】singly linked list了。
对于这类数据结构的题目往往考察的子问题一般是是对node处理, 并且往往是每次只处理一个节点。

那么现在问题来了, 挖掘机技术哪加强?

所以一般步骤如下:
A find the node need to be processed(T)
B track previous node or/ and next node of T
C process.

对于A步骤:一般常用到Runner technique 即快慢指针。
若被处理节点可能为head, 则通常在head前添加Dummy Node“


总之一句话,处理节点的方法为: 找到你要处理的那个点, 记录它的前驱后驱节点,再然后就是干干干了。

PS:以后做的list的相关题目都会更新在此贴、
e.g. Remove Nth Node From End of List


Given linked list: 1->2->3->4->5, and 【i】n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5.
  1. /**
  2. * Definition for singly-linked list.
  3. * public class ListNode {
  4. *     int val;
  5. *     ListNode next;
  6. *     ListNode(int x) {
  7. *         val = x;
  8. *         next = null;
  9. *     }
  10. * }
  11. */
  12. public class Solution {
  13.     public ListNode removeNthFromEnd(ListNode head, int n) {
  14.         ListNode dummy = new ListNode(0); // 涉及处理head节点, 添加dummy
  15.         dummy.next = head;
  16.         ListNode fast = dummy;
  17.         ListNode slow = dummy;
  18.         while(fast != null && n >= 0){
  19.             fast = fast.next;
  20.             n--;
  21.         }// 快慢指针找到要处理的节点的前驱
  22.         if(n == -1){
  23.             while(fast != null){
  24.                 slow = slow.next;
  25.                 fast = fast.next;
  26.             }
  27.             slow.next = slow.next.next;  //处理:把后驱节点 赋值给前驱节点的next。
  28.         }
  29.         return dummy.next;
  30.     }
  31. }
复制代码




2

主题

1

精华

206

积分

高级会员

Rank: 3Rank: 3

积分
206
发表于 12-2-2017 01:49 AM | 显示全部楼层
色娃加油!
回复

使用道具 举报

15

主题

12

精华

637

积分

超级会员

Rank: 4

积分
637
发表于 12-2-2017 01:56 AM | 显示全部楼层
色娃我来给你送我的半月板了
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表