单双链表的定义
单链表
在内存中定义一种数据结构，其由一个个结点链接而成，每个结点包含本结点的值和指向下一个结点的指针
单链表
代码实现：
// 单链表节点
public static class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
双链表
与单链表类似，只不过多了一个指向前驱节点的指针
双链表
代码实现
// 双链表节点
public static class DoubleListNode {
public int value;
public DoubleListNode last;
public DoubleListNode next;
public DoubleListNode(int v) {
value = v;
}
}
单双链表的反转
采用前后指针的方法，将每一个节点的next指向前驱节点即可
//单链表反转
public ListNode reverseList(ListNode head) {
ListNode pre=null;//指向前驱
ListNode nex=null;//指向后继
while(head!=null){
nex=head.next;
head.next=pre;
pre=head;
head=nex;
}
return pre;
}
而双链表的反转，反转前后链表的结构其实是一样的，只不过节点的last和next指针需要进行修改
//双链表反转
public DoubleListNode reverseDoubleList(DoubleListNode head) {
DoubleListNode pre=null;
DoubleListNode nex=null;
while(head!=null){
nex=head.next;
head.next=pre;
head.last=nex;
pre=head;
head=nex;
}
return pre;
}
