3.4 从无头链表中删除给定的结点遍历一次逆转链表

本文主要是介绍3.4 从无头链表中删除给定的结点遍历一次逆转链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 前言

本文的一些图片, 资料截取自编程之美

2. 问题描述

这里写图片描述

3. 问题分析

第一个问题 : 因为给出的只是一个链表的结点, 来删除当前结点, 所以想要找出当前结点的前一个结点貌似不可能, 所以只有另想一种方法了
这里的方法是 : “狸猫换太子”, 将下一个元素的数据复制到当前结点上面, 然后在删除下一个元素, 已达到”删除当前结点”的目的

第二个问题 : 记录下当前结点的下一个结点的下一个结点, 然后在更新下一个结点到当前结点的引用, 在更新当前结点的引用, 继续迭代，
可以有循环和递归两种处理方法, 但是最后一定要注意更新链表的头结点

4. 代码

/*** file name : Test06DelFromNoneHeadPointerLinkedList.java* created at : 9:16:16 AM May 28, 2015* created by 970655147*/package com.hx.test04;public class Test06DelFromNoneHeadPointerLinkedList {// 目的 给定一个单链表的一个指针, 然后移除该单链表的该指针处的值// 反转链表public static void main(String []args) {LinkedList ll = new LinkedList();
//      LinkedList02 ll = new LinkedList02();ll.add(4);ll.addLast(2);ll.addFirst(5);ll.addLast(34);ll.addFirst(51);Log.log(ll);Node cur = ll.head;cur = cur.next;cur = cur.next;Log.log(cur.data);delFromNoneHeadPointerLinkedList01(cur);Log.log(ll);//      reverseHeadPointerLinkedList01(ll.head);reverseHeadPointerLinkedList02(ll.head);Log.log(ll);}// 思路 : 将cur.next结点的元素复制给cur结点的元素  然后删除掉cur.next结点即可public static void delFromNoneHeadPointerLinkedList01(Node cur) {if(cur == null) {return ;}if(cur.next != null) {Node next = cur.next.next;cur.data = cur.next.data;cur.next = next;} else {Log.log("input Ref is tail node..");}}// 给出头结点 实现便利一次  反转链表// 先置空第一个结点[不是头结点].next  然后在利用next, nNext两个变量反转链表// 中间过程用到了tmp 一个临时变量[指向nNext.next  用于更新nNext]// 最后 更新head.next 为next结点public static void reverseHeadPointerLinkedList01(Node head) {if(head == null) {return ;}Node next = head.next, nNext = next.next;next.next = null;while (nNext != null) {Node tmp = nNext.next;nNext.next = next;next = nNext;nNext = tmp;} head.next = next;}// 反转链表  递归实现public static void reverseHeadPointerLinkedList02(Node head) {if(head == null) {return ;}if(head.next != null && head.next.next != null) {Node cur = head.next.next;head.next.next = null;recurselyReverseList(head.next, cur, cur.next, head);}}// 将cur.next指向prev之后   更新prev, cur, next 递归     知道cur为null   表示反转完毕private static void recurselyReverseList(Node prev, Node cur, Node next, Node head) {if(cur == null) {head.next = prev;return ;}cur.next = prev;prev = cur;cur = next;if(next != null) {next = next.next;} else {next = null;}recurselyReverseList(prev, cur, next, head);}// 单向链表的实现 [存在默认头结点]// 从实现需要考虑的方面  来说没有默认的头结点需要考虑头尾问题// 而存在默认头结点  则不太需要, 不明白为什么LinkedList为什么要采用后者,,,public static class LinkedList {Node head;Node tail;int size;public LinkedList() {head = new Node(-1, null);tail = head;size = 0;}public Node first() {return head.next;}// 添加一个元素到链表末尾public void add(int ele) {Node newNode = new Node(ele, null);tail.next = newNode;tail = newNode;size ++;}public void addNode(Node node) {tail.next = node;tail = tail.next;size ++;}// 添加一个元素到链表头public void addFirst(int ele) {add(0, ele);}// 添加一个元素到链表末尾public void addLast(int ele) {add(ele);}// 添加一个元素到链表指定索引处public void add(int idx, int ele) {Node pred = head, next = null;for(int i=0; i<idx; i++) {pred = pred.next;}next = pred.next;Node newNode = new Node(ele, next);pred.next = newNode;if(idx == size) {tail = tail.next;}size ++;}// 移除指定索引的链表元素public void remove(int idx) {Node pred = head, next = null;for(int i=0; i<idx; i++) {pred = pred.next;}next = pred.next.next;// 处理删除尾节点if(pred.next == tail) {tail = pred;}pred.next = next;size --;}// 移除值为指定值的链表元素public void removeForValue(int val) {Node pred = head, next = null;while(pred.next != null && pred.next.data != val) {pred = pred.next;}if(pred != null) {// 处理删除尾节点if(pred.next == tail) {tail = pred;}next = pred.next.next;pred.next = next;size --;}}// 获取指定索引的链表元素public int get(int idx) {Node pred = head.next;for(int i=0; i<idx; i++) {pred = pred.next;}return pred.data;}// 获取指定值的索引public int[] indexOf(int val) {Node pred = head;int idx = 0;int[] res = new int[0];while((pred = pred.next) != null ) {if(pred.data == val) {int[] newRes = new int[res.length + 1];System.arraycopy(res, 0, newRes, 0, res.length);newRes[newRes.length - 1] = idx;res = newRes;}idx ++;}return res;}// Debugpublic String toString() {StringBuilder sb = new StringBuilder(size << 3);Node cur = head;while((cur = cur.next) != null) {sb.append(cur.data + " -> ");}return sb.substring(0, sb.length() - 4);}}// 单向链表的实现 [不存在存在默认头结点]static class LinkedList02 {Node head;Node tail;int size;public LinkedList02() {head = tail = null;size = 0;}// 添加一个元素到链表末尾public void add(int ele) {Node newNode = new Node(ele, null);if(size == 0) {head = tail = newNode;} else {tail.next = newNode;tail = newNode;}size ++;}// 添加一个元素到链表头public void addFirst(int ele) {add(0, ele);}// 添加一个元素到链表末尾public void addLast(int ele) {add(ele);}// 添加一个元素到链表指定索引处public void add(int idx, int ele) {if(idx == 0) {if(size == 0) {Node newNode = new Node(ele, null);head = tail = newNode;} else {Node newNode = new Node(ele, head);head = newNode;}return ;}Node pred = head, next = null;for(int i=1; i<idx; i++) {pred = pred.next;}next = pred.next;           Node newNode = new Node(ele, next);pred.next = newNode;if(pred == tail) {tail = tail.next;}size ++;}// 移除指定索引的链表元素public void remove(int idx) {if(idx == 0) {head.data = 0;head = head.next;// 链表只有一个元素的情况下if(size == 1) {tail = head;}size --;return ;}Node pred = head, next = null;for(int i=1; i<idx; i++) {pred = pred.next;}next = pred.next.next;pred.next = next;size --;}// 移除值为指定值的链表元素public void removeForValue(int val) {Node pred = head, next = null;if(pred.data == val) {remove(0);}while(pred.next != null && pred.next.data != val) {pred = pred.next;}if(pred != null) {next = pred.next.next;pred.next = next;size --;}}// 获取指定索引的链表元素public int get(int idx) {Node pred = head;for(int i=0; i<idx; i++) {pred = pred.next;}return pred.data;}// 获取指定值的索引public int[] indexOf(int val) {Node pred = head;int idx = 0;int[] res = new int[0];while(pred != null ) {if(pred.data == val) {int[] newRes = new int[res.length + 1];System.arraycopy(res, 0, newRes, 0, res.length);newRes[newRes.length - 1] = idx;res = newRes;}pred = pred.next;idx ++;}return res;}// Debugpublic String toString() {StringBuilder sb = new StringBuilder(size << 3);Node cur = head;while(cur != null) {sb.append(cur.data + " -> ");cur = cur.next;}return sb.substring(0, sb.length() - 4);}}// 结点元素public static class Node {int data;Node next;String buildTime;// 初始化public Node() {super();this.buildTime = new Date().toString();}public Node(int data, Node next) {this();this.data = data;this.next = next;}// setter & getterpublic int getData() {return data;}public void setNext(Node next) {this.next = next;}public Node getNext() {return this.next;}// for debug ...public String toString() {return data + buildTime;}}}