乐趣区

关于算法:链表反转

要求进行链表反转
实现:

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.

退出移动版