共计 1376 个字符,预计需要花费 4 分钟才能阅读完成。
要求进行链表反转
实现:
public class ReverseList {public static void main(String[] args) {Node head = new Node(1);
Node node1 = new Node(2);
Node node2 = new Node(3);
Node node3 = new Node(4);
head.next = node1;
node1.next = node2;
node2.next = node3;
Node first = head;
while(first != null){System.out.println(first.getValue());
first = first.getNext();}
System.out.println("-----------");
head = reverseList(head);
while(head != null){System.out.println(head.getValue());
head = head.getNext();}
}
/**
* 递归
* @param head
* @return
* 思维:从后往前逆序反转指针域的指向
*/
public static Node reverse(Node head){if(head == null || head.getNext() == null)return head;
Node newHead = reverse(head.getNext());
Node temp = head.getNext();
temp.setNext(head);
head.setNext(null);
return newHead;
}
/**
* @param head
* @return
* pre: 上一节点
* cur: 以后节点
* tmp: 长期节点,用于保留以后节点的下一节点
* 思维:从前往后反转各个节点的指针域的指向
* 过程:与替换两变量的值一样,先应用一个长期变量保留以后节点的下一节点,而后替换 pre 与 cur 节点
*/
public static Node reverseList(Node head){if(head == null){return head;}
Node pre = head;
Node cur = head.getNext();
Node tmp;
while(cur != null){tmp = cur.getNext();
cur.setNext(pre);
pre = cur;
cur = tmp;
}
head.setNext(null);
return pre;
}
}
class Node<E>{
int value;
Node next;
Node(int x){value = x;}
public int getValue() {return value;}
public void setValue(int value) {this.value = value;}
public Node getNext() {return next;}
public void setNext(Node next) {this.next = next;}
}
这里有一张图阐明下就地反转的思维:
dummy 为头节点
prev 连贯下一次须要反转的节点
pCur 指向下一次须要反转的节点
伪代码:
prev.next = pCur.next;
pCur.next = dummy.next;;
dummy.next = pCur;
pCur = prev.next;
始终循环直到 pCur 指向的节点为 null.
正文完